소수 판별하기

1. 소수 판별 법

#include <iostream>
#include <cmath> // sqrt 함수를 사용하기 위해 필요

bool isPrime(int n) {
    if (n <= 1) { // 1 이하는 소수가 아니다
        return false;
    }
    if (n == 2) { // 2는 유일한 짝수 소수
        return true;
    }
    if (n % 2 == 0) { // 2를 제외한 짝수는 소수가 아니다
        return false;
    }
    // 3부터 시작해서 홀수만 검사하면 된다
    // n의 제곱근까지만 검사해도 충분하다
    for (int i = 3; i <= sqrt(n); i += 2) { 
        if (n % i == 0) { // 나누어 떨어지면 소수가 아니다
            return false;
        }
    }
    return true; // 위에 해당 안되면 소수
}

 

 

2. 에라토스테네스의 체 (범위 내의 소수 구하기)

#include <iostream>
#include <vector>
#include <cmath> // sqrt 함수를 사용하기 위해 필요

void primenumber(int limit) {
    // limit + 1 크기의 불리언 배열을 만들고 모두 true로 초기화
    // isPrime[i]가 true이면 i는 소수, false이면 소수가 아님
    std::vector<bool> isPrime(limit + 1, true);

    // 0과 1은 소수가 아니니까 false로 표시
    isPrime[0] = false;
    isPrime[1] = false;

    // 2부터 숫자의 제곱근까지만 검사하면 된다
    for (int p = 2; p * p <= limit; ++p) {
        // p가 소수라면 p의 배수들을 모두 지운다
        if (isPrime[p]) {
            // p*p부터 limit까지 p의 배수들을 false로 표시
            // (p*2, p*3 등은 이미 p보다 작은 수의 배수에서 걸러진다)
            for (int i = p * p; i <= limit; i += p) 
                isPrime[i] = false;
        }
    }

    // 소수들을 출력
    std::cout << limit << "까지의 소수: ";
    for (int p = 2; p <= limit; ++p) {
        if (isPrime[p]) {
            std::cout << p << " ";
        }
    }
    std::cout << std::endl;
}

int main() {
    primenumber(30); // 30까지의 소수를 찾는다
    return 0;
}