백준 1929번 : 소수 구하기 - 에라토스테네스의 체 (C++, Python)

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

 

1978번 문제의 업그레이드 버전이다.

1978번을 풀지 않았다면 먼저 풀어보고 오는 걸 추천한다.

https://coding-yeou.tistory.com/3

백준 1978번 : 소수 찾기 (C++,Python)

위 문제에서는 범위가 최대 1,000인 100개의 수를 탐색하면 돼서 전부 돌려볼 수 있었다.

하지만 이번 문제는 범위가 최대 1,000,000이고 1,000,000개의 수를 전부 탐색해야 해서 1978의 풀이로는 시간초과를 받는다.

 

빠른 소수 판정 알고리즘 

소수를 구하는데 가장 많이 쓰이는 알고리즘으로 에라토스테네스 체가 있다.

다음과 같은 원리로 동작한다.

 

만약 2가 소수라면 2를 제외한 2의 배수들은 소수가 아니다.

만약 3이 소수라면 3을 제외한 3의 배수들은 소수가 아니다.

만약 5가 소수라면 5를 제외한 5의 배수들은 소수가 아니다.

...

만약 N이 소수라면 N을 제외한 N의 배수들은 소수가 아니다.

 

에라토스테네스의 체 알고리즘은 위와 같은 사실을 이용해서 그물망으로 소수를 거르듯이 판정한다.

자세히는 아래처럼 그림과 같이 동작한다.

1. 소수를 판별하고 싶은 범위(N)만큼의 bool 배열 sieve을 만든다.

2. 2~N까지의 i를 순차적으로 탐색한다.

- sieve[i]가 True이라면(소수가 아니라면) 다음 수를 탐색한다.

- sieve[i]가 False이라면(소수라면) i를 제외한 i 배수를 j라 할 때 sieve[j] = True로 설정한다.

 

위의 과정을 다 마친 후 x를 판별하고자 할 때 sieve[x]가 False이면 소수, True이면 합성수이다.

 

*1은 소수가 아님에 주의하자

#1~100까지의 수 중에 소수를 출력하는 코드
N = 100
sieve = [False] * (N+1)
sieve[1] = True   # 1은 소수가 아니다
for i in range(2,N+1):
    if(sieve[i]): # i가 소수면 스킵
        continue

    for j in range(i+i, N+1, i): #아니라면 i를 제외한 i의 배수를 True:
        sieve[j] = True

for i in range(1,N+1): # 소수 출력
    if(not sieve[i]):
        print(i,end=" ")

출력 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 

꽤 연산량이 많이 보이지만 에라토스테네스의 체는 놀랍게도 시간복잡도가 O(N * log(logN))이다. log(logN)은 사실상 상수이므로 실제로 O(N)이라 생각하고 돌려도 문제가 없다.

 

풀이

이제 에라토스테네스의 체를 이용해서 1929번을 풀어봅시다.

 

M이상 N이하의 소수를 출력하는 문제이니

에라토스테네스의 체를 이용해 N까지의 소수를 전부 구하고

M~N까지의 i 중에 sieve[i]가 False인 i를 출력하면 끝!

 

C++ 정답코드

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0);

    int m,n;
    cin >> m >> n;

    vector<bool> sieve(n+1);
    sieve[1] = true;

    for(int i = 2; i<=n; i++)
    {
        if(sieve[i])	
            continue;

        for(int j = i+i; j<=n; j+=i)
            sieve[j] = true;
    }

    for(int i = m; i<=n; i++)
    {
        if(!sieve[i])
            cout << i << "\n";
    }
    return 0;
}

Python 정답코드

import sys
input = sys.stdin.readline()

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

sieve = [False] * (N+1)
sieve[1] = True
for i in range(2,N+1):
    if(sieve[i]):
        continue

    for j in range(i+i, N+1, i):
        sieve[j] = True

for i in range(M,N+1):
    if(not sieve[i]):
        print(i)

 

알아두면 좋은 것

코드에서

if(sieve[i])	
    continue;

이 부분은 사실 없어도 되는 부분이에요.

왜냐면 소수가 아닌것의 배수는 모두 소수가 아니기 때문에 연산량이 많아질 뿐 별다른 문제는 없어요.

(N/2 + N/3 + N/5 + N/7 + ... -> N/2 + N/3 + N/4 + N/5 + ...로 늘어납니다)

 

조화수열 : N/2 + N/3 + N/4 + N/5 + ... = N*logN

에라토스테네스의 체 : N/2 + N/3 + N/5 + N/7 + ... = N*log(logN)

위 2개의 사실은 ps에서 중요하게 쓰이니 알아두면 좋아요!