에라토스테네스의 체

에라토스테네스의 체

수학자 에라토스테네스에 의해 만들어진 소수를 빠르게 찾을 수 있는 알고리즘이다

자기자신을 제외한 수의 배수들을 지워나가는 과정을 통해 소수만 빠르게 남길 수 있다

이 과정에서 어떤 수의 배수들을 지우기 전에 이미 이전의 어떤 다른 수의 배수 차례가 오면 넘어가도록 함으로써 불필요한 연산을 줄일 수 있다

그리고 정수론의 다음 증명을 통해 수의 범위를 줄일 수 있다

소수는 n의 배수가 아니어야 한다.
입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.
그러나 모두 나누어볼 필요없이, $\sqrt{n}$ 까지만 나누어서 떨어지면 소수가 아니다.

이 증명을 통해 1부터 n까지 소수를 판정할 때 보다는 1부터 $\sqrt{n}$까지만 확인하면 된다

[2153] 소수 단어를 풀면서 소수 판별을 해보자

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> get_prime() {
    vector<int> p;
    for (int i = 0; i <= 1050; i++) p.push_back(i);

    for (int k = 2; k < int(sqrt(1050))+1; k++) {
        for (int x = pow(k, 2); x <= 1050; x+=k) p[x] = 0;
    }

    return p;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string target; cin >> target;
    int value = 0;

    for (int i = 0; i < target.length(); i++) {
        if ('a' <= target[i] && target[i] <= 'z') value += target[i] - 'a' + 1;
        else value += target[i] - 'A' + 27;
    }

    vector<int> p = get_prime();
    
    if (p[value] != 0) cout << "It is a prime word.";
    else cout << "It is not a prime word.";
}