普通：

bool prime(int n){
    if(n < 2){
        return false;
    }
    for(int i = 2;i <= floor(sqrt(n));i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

埃氏筛：

#include<bits/stdc++.h>
using namespace std;
const long long MAX = 1e10;
long long a[MAX], n;
int main(){
    cin >> n;
    a[0] = 0;
    for(long long i = 1;i <= n;i++){
        a[i] = i;
        a[1] = 0;
    }
    for(long long i = 2;i <= n;i++){
        if(a[i] == 0) continue;
        printf("%d, ", i);
        for(long long j = i;i * i <= n && j < n;j++){
            a[i * j] = 0;
        }
    }
    return 0;
}