[백준/c++] 1929번: 소수 구하기

 

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

1929번: 소수 구하기

 

 

문제를 풀기 전에, 소수를 찾는 굉장히 빠른 유명한 알고리즘이 있다. 이 알고리즘부터 구현해보고 가자.

 

에라토스테네스의 체

: 소수를 찾는 방법 (대량의 소수를 구할 때, 아주 유용한 알고리즘 O(N^1/2)

  → 1을 제외한 수의 배수가 되는 수는 소수가 아님

       임의의 수 n까지의 소수를 구하고자 할 때 2부터 n의 제곱근까지 돌면 모든 배수들을 소수에서 제외시키는 방식

 

배열을 통해서 소수에서 제외했는지 안 했는지를 관리할 수 있다.

1. 2는 소수이므로 제외하고 n까지 2의 배수들을 0으로 치환 (2의 배수 == 짝수, 모두 제외)

2. 3은 소수이므로 제외하고 n까지 3의 배수들을 0으로 치환 (3의 배수, 소수 아님, 모두 제외)

3. 반복 (이전 수의 배수가 되는 값들은 continue)

4. 0이 아닌 수 출력 (소수)

 

void primeNumber(){
    for(int i=2; i<=n; i++) prime[i] = i;
    for(int i=2; i<=sqrt(n); i++){
        if(prime[i]==0) continue;
        for(int j=i*i; j<=n; j+=i) prime[j] = 0;
    }

    for(int i=2; i<=n; i++) if(prime[i] != 0) cout << prime[i] << '\n';
}

 

 

 

---

 

M이상 N이하 수 중 소수들만 출력

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int m, n;
int num[1000001];

void primeNumber(){
    for(int i=2; i<=n; i++) num[i] = i;
    for(int i=2; i<=sqrt(n); i++){
        if(num[i] == 0) continue; //num[i]가 0이면 소수가 아니므로 continue
        for(int j=i*i; j<=n; j+=i) num[j] = 0; //i*k(i<k)까지의 수는 이미 검사했으므로 i*i부터 검사
    }
    for(int i=m; i<=n; i++) if(num[i] != 0) cout << num[i] << '\n'; //출력
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    primeNumber();
    return 0;
}