소수 여부 판별

1. 소수 여부 판별 개념

https://smallpants.tistory.com/161

 

2. C++ style Code

1) 숫자 N 1개만 소수인지 판별하면 될때는 2부터 sqrt(N)까지 나눠본다.

bool is_primenumber(int n) 
{
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false; 
    } 
    return true; 
}

 

2) 소수인지 판별해야 할 수가 여러개라면 for문을 쓸데없이 여러번 반복할 필요가 없다.
메모이제이션을 사용하는 에라토스테네스의 체 알고리즘을 사용한다.

std::vector<bool> primenumber_table;

void makePrimeNumberTable(int max) // 에라토스테네스의 체
{    
    primenumber_table.resize(max + 1, true);
    primenumber_table[0] = false;
    primenumber_table[1] = false;

    for (int i = 2; i <= sqrt(max); i++) {
        if (primenumber_table[i])    {
            for (int j = 2 * i; j <= max; j += i) {
                primenumber_table[j] = false;
            }
        }
    }
}