[이코테/소수/C++] 소수, 약수, 에라토스테네스의 체 *

 

#include <bits/stdc++.h>

using namespace std;

// 소수 판별 함수(2이상의 자연수에 대하여)
bool isPrimeNumber(int x){
    // 2부터 x의 제곱근까지의 모든 수를 확인하며
    for(int i=2; i<=(int)sqrt(x); i++){
        // x가 해당 수로 나누어 떨어진다면
        if(x%i == 0){
            return false; // 소수가 아님
        }
    }
    return true; // 소수임
}

int main(){
    cout << isPrimeNumber(4) << '\n';
    cout << isPrimeNumber(7) << '\n';

    return 0;
}

 

에라토스테네스의 체

#include <bits/stdc++.h>

using namespace std;

int n = 1000; // 2부터 1000까지의 모든 수에 대하여 소수 판별
vector<int> arr(n+1, true); // 처음엔 모든 수가 소수(true)인 것으로 초기화

int main(){
    // 에라토스테네스의 체 알고리즘 수행
    for(int i=2; i<=(int)sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인하며
        if(arr[i] == true){ // i가 소수인 경우(남은 수인 경우)
            // i를 제외한 i의 모든 배수를 지우기
            int j=2;
            while(i*j <= n){
                arr[i*j] = false;
                j += 1;
            }
        }
    }
    for(int i=2; i<=n; i++){ // 모든 소수 출력
        if(arr[i]) cout << i << ' ';
    }

    return 0;
}