에라토스테네스의 체 [알고리즘 공부][정수론]

에라토스테네스의 체(sieve of Eratosthenes)는 2이상 n 이하의 정수 x가 소수인지 판별하는 알고리즘이다.

다음은 n=10일때의 작동원리이다.

2부터 시작하여 새로운 소수 x를 발견할 때마다 2x,3x,4x...를 소수가 아니라 체크한다.

이러한 과정을 통해 시간 복잡도를 O(n log log n)까지 줄일 수 있다.

 

또한 이를 최적화 할 수 있는 방법이 몇가지 있다.

1.새로운 소수 x를 발견할때마다 2x,3x,4x...를 소수가 아니라 체크하므로 x^2이 n보다 작을 때 까지만 실행하면 된다.

2.새로운 소수 x를 발견하면, x부터 시작하는 것이 아닌 x^2부터 시작하면 된다. 이유는 그 사이값들은 이미 x보다 작은 소수들에 의해 체크되었기 때문이다.

 

이를 이용하여 간단한 백준 문제를 연습해보고 끝내겠다.

 

4948 - 베르트랑 공준(실버 2)

https://www.acmicpc.net/problem/4948

n부터 2*n까지의 소수의 개수를 구해주면 된다.

while True:
    n=int(input())
    if(n==0):break
    sieve = [0]*(2*n+1)
    p=2
    while (p*p <= 2*n):#루트 n까지만
        if(sieve[p]==0):#만약 소수라면
            for i in range(p*p, 2*n + 1,p):sieve[i]=1#p^2부터 2*n까지
            
        p+=1
    sieve = sieve[n+1:2*n+1]
    print(sieve.count(0))