[알고리즘]에라토스테네스의 체

소수를 찾는 방법으로 하나 외우고 있으면 좋을것 같다

소수를 찾는 코테 문제하나를 풀어봤는데 기존에 모든 경우의 수(2와 3부터 시작하는 모든 홀수)

를 넣어서 찾는 방법은 시간초과가 되어버렸다.(소수탐색 자체만 해도 O(n)이고 만약 두 소수의 곱으로 이뤄진 숫자에서 두 소수를 찾아라 하는 문제일 경우 반복문을 이용해야 되므로 O(n^2)의 경우가 되는 문제가 있었다.)

에라토스테네스의 체를 사용한다면 O(N^1/2)의 시간복잡도로 계산할수 있다

주로 대량의 소수를 한꺼번에 판별해야할 경우에 사용한다

• 방식(파이썬)

  • 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다
    2. 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지운다.
    3. 3도 지워지지 않았기 때문에 소수로 선택하고 3의 배수를 지운다
    4. 4는 지워졌기 때문에 넘어가고 5를 소수로 선택학고 5의 배수를 지운다.
    5. 2,3,4와 같은 과정을 반복한다
    6. 반복이 끝나면 지워지지 않은 수들을 소수로 출력한다.가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 

• 소스코드

  n=100
      a = [True] * n+1
      #n의 최대 약수는 sqrt(n) 이하이므로 i=sqrt(n)까지 검사한다.
      #루트의 경우 sqrt대신 **0.5로 사용하였다.
      m = int(n**0.5)
      
      for i in range(2,m+1):
      	if a[i] == True:
      		for j in range(i+i,n+1,i):
      			a[j] = False
      print([i for i in range(2,n+1) if a[i] == True])