백준 1929 - 소수 구하기 [파이썬]

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

1929번: 소수 구하기

 

 

풀이 과정

소수 찾기 문제처럼 각각의 수에 대해 소수 판정을 하면 시간 초과가 난다. 소수를 판정하는 알고리즘의 시간 복잡도는 O(rootN)인데 1이상 100만 이하의 소수를 구하라는 입력이 들어올 수 있다.

 

100만 * root 100만 = 대략 10억번 가량의 연산이 필요하고 시간 제한 2초내로 해결할 수 없다.

 

특정 범우의 모든 소수를 구할 때는 에라토스테네스의 체라는 알고리즘을 활용해야 한다. 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 수를 적어놓고

2. 남아있는 수중 가장 작은수를 검색하고

3. 그 수를 소수라고 한다음에

4. 그 수의 배수는 모두 소수가 아니니 지워 없앤다

int prime[100]; // 소수를 저장하는 배열
int pn = 0; // 소수의 개수
bool check[101]; // 지워졌으면 true로 체크한다
int n = 100; // n 까지의 소수를 구하겠다

for (int i = 2; i <= n; i++) {
	if (check[i] == false) {
    	prime[pn++] = i;
        for (int j = 2*i; j <= n; j += i) {
        	check[j] = true;
        }
    }
}

 

prime = []
check = [0] * 101
n = int(input())
for i in range(2, n+1):
    if check[i] == 0:
        prime.append(i)
        for j in range(2*i, n+1, i):
            check[j] = 1

 

c++와 파이썬으로 구현한 에라토스테네스의 체 알고리즘이다. 에라토스테네스의 체로 2부터 N까지의 모든 소수를 구하는 시간복잡도는 O(NloglogN)으로 알려져 있으므로 시간 제한내에 문제를 해결할 수 있다.

코드

prime = []
primeCheck = [0] * 1000001

M, N = map(int, input().split())

for i in range(2, N+1):
    if primeCheck[i] == 0:
        prime.append(i)
        for j in range(2*i, N+1, i):
            primeCheck[j] = 1

for i in prime:
    if i >= M: print(i)