에라토스테네스 최적화, 소수 판별

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

typedef long long ll;
bool ch[200];
bool Prime[200];


bool isPrime(int num){
    for(int i=2; i*i <=num; i++){
        if(num%i==0) return false;
    }
    return true;
}


//소인수분해
vector<ll> factorSimple(ll n){
    vector<ll> ret;

    ll sqrtn = ll(sqrt(n));
    for(ll div = 2; div<=sqrtn; div++){
        while(n%div==0){
            n/=div;
            ret.push_back(div);
        }
    }
    if(n>1) ret.push_back(n);

    return ret;
}

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

    ch[0] = 1;

    for(int i=2; i<100; i++){
        cout << i << ' ';
        if(isPrime(i)) cout << "is Prime" << '\n';
        else cout << "is not Prime" << '\n';
    }

    
    
    //slow erathostenes
    for(int i=2; i<200/2 + 1; i++){
        if(ch[i]==0){
            for(int j=i+i; j<200; j+=i){
                ch[j] = 1;
            }
        }
    }

    //fast erathostenes;
    int sqrtn = int(sqrt(200));
    for(int i=2; i<=sqrtn; i++) {
        if (Prime[i])
            for (int j = i * i; j <= 200; j++) {
                Prime[i] = 1;
            }
    }
    
    
    return 0;
}

i 가 루트 n보다 큰 경우에는

이미 이전에 계산한 적이 있기 때문에 생략할 수 있고,

j가 i*i보다 작은 경우도 마찬가지로

i가 i-1이하일 때 이미 계산된 적이 있기 때문에 생략할 수 있다.

 

그래서 보다 에라스토테네스 알고리즘을 최적화 할 수 있다.