소수 판별

소수 판별

소수(Prime Number)를 판별하는 방법 중 한 가지 : 에라토스테네스의 체

• 2부터 시작하는 순차적인 자연수의 집합이 있다고 하자. ex) 2, 3, 4, 5, 6, ..., 120
• 자기자신을 제외한 2의 배수를 모두 지운다.
• 남은 수 중 다음 수는 3
• 자기자신을 제외한 3의 배수를 모두 지운다.
• 남은 수 중 다음 수는 5
• 자기자신을 제외한 5의 배수를 모두 지운다.
• 이 과정을 반복하면 해당 집합에서 소수만 남는다.

중요한 점

• 이 과정에서 120^(0.5) < 11 이므로 11보다 작은 수의 배수들 까지만 지우면 된다.
• (13의 배수, 17의 배수 등 지울 필요 없음...)
• 왜 ????
• 예를 들어서 7의 배수를 지우고 있다고 하자7*3 = 21 ... 7*16 = 112 7*17 = 119이렇게 119 까지 지웠다!
• 이어서, 8의 배수는 2의 배수를 지울 때 다 지워졌고
• 9의 배수, 10의 배수도 마찬가지로 이미 지워졌다.
• 11의 배수를 지워보자11*2 = 22 11*3 = 33 11*4 = 44 11*5 = 55 11*6 = 66 11*7 = 77 11*8 = 88 11*9 = 99 11*10 = 110 11*11 = 121근데 생각을 해보자... 11*2 를 지우려는데, 이건 2의 배수를 지울 때 지웠고,11*10 도 10의 배수를 지울 때(2의 배수를 지울 때) 지웠다!!!
• 11*11 은 120 이 넘으니까 지울 필요가 없다.
• 11*3도 3의 배수를 지울 때 지웠다.
• **이러한 이유로 2부터 N까지의 자연수 집합 중에서 소수를 구하고 싶다면,** int(N^(0.5)) + 1 # int() 는 내림 이다.**미만인 수들의 배수들만 지워도 된다.**

파이썬 코드

sieve = [True] * N # 0부터 N까지... # sieve[소수] == True 가 되도록 만들거임 sieve[0] = False sieve[1] = False # 0과 1은 소수 아님.. 처리 for i in range(2, int(N ** 0.5) + 1) : # 2부터 배수들 지우기 if sieve[i] == True : for j in range(i*2, N, i) : sieve[j] = False # 자기자신 제외 배수들 지우기

**왜 N의 제곱근 까지만 지워도 되는지 궁금한 사람들에게 도움이 되었으면 한당 ^^**

-dnlxo