本人发现的一个奇奇怪怪的质数筛法

Kevin____ · 2025-05-18 20:53:56 · 算法·理论

#include<bits/stdc++.h>
using namespace std;
vector<int> isprime(1,1);
int n;
bool pd(int x){
    for(int i=0;i<isprime.size()&&isprime[i]*isprime[i]<=x;i++){
        if(x%isprime[i]==0){
            return 0;
        }
    }
    return 1;
}
int main()
{
    cin>>n;
    isprime[0]=2;
    cout<<2<<' ';
    for(int i=3;i<=n;i++){
        if(pd(i)){
            isprime.push_back(i);
            cout<<i<<' ';
        }
    }
    return 0;
}
时间：O（  $ n \sqrt{n} $  ）
空间：O(k)