소수 구하기

소수를 구하는 여러 알고리즘들이 있지만 그중에서 자주 사용되는 것은

에라토스테네스의 체이다.

 

한번 틀을 짜놓고 외우면 이후에 쉽게 사용 가능하다.

 

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<bool> sieve;
 
void era(int n) {
    sieve.resize(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= n; ++i)
        if (sieve[i])
            for (int j = i * 2; j <= n; j += i)
                sieve[j] = false;
}
 
int main() {
    int n;
 
    cin >> n;
    era(n);
 
    for (int i = 2; i <= n; ++i)
        if (sieve[i]) cout << i << '\n';
 
    return 0;
}

 

그 외에도 비트마스크를 이용해서 소수를 구하면 메모리를 무려 1/8이나 절감시킬 수 있다.

 

 

const int MAX = 1e6;
unsigned char sieve[(MAX + 7) / 8 + 1];
 
bool isPrime(int k) {
    return sieve[k >> 3] & (1 << (k & 7));
}
 
void setComposite(int k) {
    sieve[k >> 3] &= ~(1 << (k & 7));
}
 
void era() {
    fill(sieve, sieve + (MAX + 7) / 8, 255);
    setComposite(0);
    setComposite(1);
 
    for (int i = 0; i * i <= MAX; ++i)
        if (isPrime(i))
            for (int j = i * 2; j <= MAX; j += i)
                setComposite(j);
}

 

이런 식으로 전처리해주고 사용하면 된다.