소수 판별 알고리즘 - 에라토스테네스의 체

#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321

#include <iostream>
#include <math.h>

using namespace std;

// 시간복잡도 O(N^(1/2)
bool prime(int x) {

    int end = (int)sqrt(x);

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

// 많은 양을 판단해야 할 때 -> 에라토스테네스의 체
// 먼저, 판별할 범위만큼 배열을 할당

int num[101]; // 2~100까지

void primeNumber() {
    
    for (int i = 2; i <= 100; i++) {
        num[i] = i;
    }

    for (int i = 2; i <= 100; i++) {
        if (num[i] == 0) continue;
        for (int j = i + i; j <= 100; j += i) {
            num[j] = 0;
        }
    }

    for (int i = 2; i <= 100; i++) {
        if (num[i] != 0) cout << num[i] << " ";
    }
}


int main() {

    cout << prime(8) << endl;
    
    primeNumber();


    return 0;
}