소수 찾기 알고리즘

[devLupin]

에라토스테네스의 체

• 한번에 전부 계산하는 게 이로울 때 사용하자
• 자료형 bool로 쓰기!

#include <cmath>

using namespace std;

bool arr[1000001];

int eratos(int n) {
    fill_n(arr, n, true);

    for(int i=2; i<=sqrt(n); i++) {
        if(!arr[i]) 
            continue;

        for(int j=i*i; j<=n; j += i)
            arr[j] = false;
    }

    int ans = 0;
    for(int i=2; i<=n; i++)
        if(arr[i]) ans++;

    return ans;
}

[devLupin]

10진수 num이 소수인지 판별

• 하나의 10진수만 구할 때 유용하다.
• 자료형은 long long 형으로..
• 소수라면 true return

using ll = long long;

bool is_prime(ll num) {
    if(num < 2) return false;

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