1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수
소수인지 검사하는 함수(isPrime)를 만든다.
isPrime() 함수는 1을 제외하고,
2부터 해당하는 자연수까지 판별할 숫자들을 하나씩 순회하면서 소수 여부를 판별한다.
따라서, 범위가 매우 큰 경우에는 많은 시간이 소요될 수 있다.
1부터 100 사이의 소수를 구하는 파이썬 코드를 작성하면 다음과 같다.
n = 100
def isPrime(a):
if (a < 2):
return False
for i in range(2, a):
if (a % i == 0):
return False
return True
for i in range(n+1):
if(isPrime(i)):
print(i)
위의 코드는 해당 수보다 작은 모든 수로 나누어 소수인지를 판단하는 방법이다.
한 개의 소수를 구할 때는 괜찮지만 해당 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.
따라서, 소수를 구할 때는 에라토스테네스의 체를 이용하는 것이 좋다.
해당 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법
1은 소수가 아니므로 제거
지워지지 않은 수 중 가장 작은 2를 소수로 채택하고,
나머지 2의 배수를 모두 지운다.
지워지지 않은 수 중 가장 작은 3을 소수로 채택하고,
나머지 3의 배수를 모두 지운다.
지워지지 않은 수 중 가장 작은 5를 소수로 채택하고,
나머지 배수를 모두 지운다.
(반복)
에라토스테네스의 체를 파이썬 코드로 표현하면 다음과 같다.
n = 1000
a = [False, False] + [True] * (n-1)
primes = []
for i in range(2, n+1):
if a[i]:
primes.append(i)
for j in range(2*i, n+1, i):
a[j] = False
print(primes)