에라토스테네스의 체

일반적으로 특정 숫자(N)의 소수 여부는 제곱근 까지의 약수 여부를 검증하여 확인한다.

N을 나누는 약수가 있다면, 해당 약수 또는 몫 둘 중 하나는 N 제곱근 이하이기 때문이다.

 

대량의 소수를 판단해야 할 때, '에라토스테네스의 체' 원리를 이용한다.

소수를 판별할 범위만큼 배열을 할당한 후, 해당하는 값을 넣어주고, 하나씩 지워가는 방법이다.

1) 배열 생성

2) 2부터 시작하여, 특정 수의 배수에 해당하는 수를 모두 지움

3) 2부터 시작하여, 남아있는 수는 소수이므로, 모두 출력

 

number = 100000
a=[]*100001

# 배열 생성하여 초기화
for i in range(2, number+1):
	a[i] = i;

# 2부터 시작하여, 특정 수의 배수에 해당하는 수를 지운다.
# (특정 수의 크기를 간격으로 정하면 됨)
for j in range(2, number+1):
	for k in range(2*j, number+1, i):
    	a[j] = 0

# 2부터 시작하여 남아있는 수를 모두 출력한다.
for idx in range(2, number+1):
	if a[idx] != 0:
    	print(a[idx])

 

출처: [Algorithm ]에라토스테네스의 체