Sieve of Eratosthenes, 대량의 소수를 한꺼번에 판별 및 출력하는 알고리즘이다.
소수(prime number)는 자기자신과 1을 약수를 가지는 수이며, 에라토스테네스의 체는 특정 범위까지 소수를 출력한다.
1개의 수에 대한 소수여부를 파악하고자 하면, 수의 범위가 대칭을 이룬다는 점을 이용하여(한 수의 제곱근으로 범위를 줄여 판단 후 소수여부 확인) 해당 수의 제곱근까지만 소수인지 판단하면 된다.
#소수찾기
import math
def isPrimeNumber(n):
end = int(math.sqrt(n))
for i in range(2, end):
if n % i == 0:
return False
return True
print(isPrimeNumber(97))
number = 1000
numberArray = [0] * (number + 1)
에라토스테네스의 체는 특정 수까지 모든 소수를 출력하는 알고리즘이다.
하나의 배열에 모든 수를 넣고, 2부터(2는 제외) 2의 배수를 차례로 제거한 후 최종적으로 남은 수(소수)를 출력한다.
number = 1000
numberArray = [0] * (number + 1)
def primeNumberSieve(number):
for i in range(2, number):
numberArray[i] = i
for i in range(2, number):
if numberArray[i] == 0:
pass
else:
for j in range (i+i, i, number):
numberArray[j] = 0
for i in range(2, number):
if numberArray[i] != 0:
print(numberArray[i])
primeNumberSieve(number)