[알고리즘]소수판별

소수 구하기 - 에라토스테네스의 체

1.2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2.2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3.자기 자신을 제외한 2의 배수를 모두 지운다.
4.남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5.자기 자신을 제외한 3의 배수를 모두 지운다.
6.남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7.자기 자신을 제외한 5의 배수를 모두 지운다.
8.남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9.자기 자신을 제외한 7의 배수를 모두 지운다.
10.위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

약수

18의 약수 : 1, 2, 3, 6, 9, 18

• 1 x 18 = 18
• 2 x 9 = 18
• 3 x 6 = 18
• 6 x 3= 18
• 9 x 2 = 18
• 18 x 1= 18

약수를 기준으로 등식이 대칭을 이룸.따라서 자연수가 소수인지 확인을 위해서는 가운데 약수까지 나누어 떨어지는지만 확인. 즉, 제곱근(가운데 약수)까지만 확인.

[방법1] 반복문 활용

def is_prime_number(x):
for i in range(2,x):
	if x%i==0;
		return False #소수가 아님
return True #소수임

모든 수를 하나씩 확인->시간 복잡도 : O(N) 비효율적 😵‍💫

[방법2] 대칭활용 (개선된 알고리즘)

import math

def is_p[rime_number(x):
	for i in range(2, int(math.sqrt(x))+1):
    	if x%i==0:
        	return False #소수가 아님
    return True #소수임

시간 복잡도 : O(N^(1/2))