소수 구하기 알고리즘 : 아리토스테네스의 체

일반적 알고리즘

자기보다 작은 수로 나누어서 나누어 떨어지면 소수가 아니다.

 

n = int(input('input range number: ')) #수 입력
prime_nums = [] #소수를 저장할 리스트 생성

for i in range(2,n): #2부터 모든 수를 체크
    prime_nums.append(i) #일단 넣어
    for j in range(2,i):
        if i % j == 0: #만약 나눠지는 수가 있으면
            del prime_nums[-1] #넣었던 수 빼기
            break #다음은 볼것도 없음

print(prime_nums)

 

아리토스테네스의 체

아리스토테네스 

아리토스테네스의 체 알고리즘으로 소수를 구할 수 있다. 

1. 각 배수의 수들은 소수가 아니다 (2-> 4, 6, 8 ...)(3-> 6, 9, 12 ...)

2. 구하고자 하는 수가 range(n) 이라고 하면, $\sqrt{n}$ 까지의 수들의 배수를 지워나가면 된다.

 

n = int(input('input range number:')) #몇까지의 소수를 구할것인가
prime_range = np.arange(n)

n_max = int(np.sqrt(len(prime_range))) # root(n)까지의 배수들만 확인하면 된다.

for i in range(2,n_max):
    prime_range[2*i::i] = 0 #소수가 아닌 수는 0으로 바꾼다

np.setdiff1d(prime_range,[0,1]) #prime_range 와 [0,1] 차집합 연산

 

input range number:100

Out[19]:

array([ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])

 

for 문이 이해가 안된다면, 구구단을 거꾸로 생각하면 된다. [2*i : : i] 는 2 * i 부터 n_max 이하까지의 i단을 0으로 바꿔주는 것이다.