[Python] 소수구하기, 에라토스테네스의 체

소수

: 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수이다.

 

방법 1 자신보다 작은 모든 수로 나누어 보기

 

100이하의 모든 소수 구하기 함수 isPrime

n=100

def isPrime(a):
  #2보다 작은 수는 제외한다.
  if(a<2):
    return False
    
  #2이상 n이하 정수 중에서 나뉘어지는 수가 있으면 False 리턴
  for i in range(2,a):
    if(a%i==0):
      return False
  return True

#True를 리턴한 수만 출력한다.
for i in range(n+1):
  if(isPrime(i)):
    print(i)

 

방법 2 에라토스테네스의 체

: 위 방법은 자신보다 작은 모든 수로 나누어보는 방법으로 소수의 정의를 잘 구현한 소스이지만, 해당 범위 내의 모든 소수를 구하기에는 효율적이지 않다. 소수를 구하기 위해 에라토스테네스가 제안한 방법은 다음과 같다. 

 

-범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

1) 1은 제거

2) 지워지지 않은 수 중 가장 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지움

3) 지워지지 않은 수 중 가장 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지움

4) 지워지지 않은 수 중 가장 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지움

5) 반복

n=100

#100개의 수를 검사하기 위해 100개의 요소가 있는 리스트를 생성한다.
#0과 1에 해당하는 범위는 False로 초기화하여 검사하지 않고, 나머지는 True로 초기화한다.
a = [False,False] + [True]*(n-1)
primes=[]

#2부터 100까지 검사
for i in range(2,n+1):
  if a[i]:
    #리스트의 요소가 True 값인 수를 primes에 추가한다.
    primes.append(i)
    #2의 배수, 3의 배수, ... 100의 배수에 해당하는 100이하의 양의 정수를 False로 바꾼다.
    for j in range(2*i, n+1, i):
        a[j] = False

#True로 남아있는 수들만 출력된다.
print(primes)