质数

判断质数

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

筛法求素数【高效】

适用于判断很多数是不是质数，但不适用于数字很大的情况

欧拉筛法

bool IsPrime[7100];
int Prim[7100];
void euler_prime(int n){
    int j;
    for(int i=2;i<=n;i++){
        if(!IsPrime[i])
            Prim[++num]=i;
        for(j=1;j<=num;j++){
            if(i*Prim[j]>n)
                break;
            IsPrime[i*Prim[j]]=1;
            if(i%Prim[j] == 0)
                break;
        }
    }
}

埃拉特斯特尼筛法

    #include <bits/stdc++.h>
    using namespace std;

    const long long maxn = 10000007 + 10;
    const long long maxp = 700000;
    int vis[maxn];    // i是合数vis为1，i是素数，vis为0
    long long prime[maxp];

    void sieve(long long n){
        long long m = (long long)sqrt(n + 0.5);
        memset(vis, 0, sizeof(vis));
        vis[2] = 0;
        for (long long i = 3; i <= m; i += 2) {
            if(!vis[i])
                for (long long j = i * i; j <= n; j += i)
                    vis[j] = 1;
            if(i * i > n)
                break;
        }
    }

    long long gen(long long n){
        sieve(n);
        long long c = 1;
        prime[0] = 2;
        for (long long i = 3; i <= n; i += 2)
            if(!vis[i])
                prime[c++] = i;
        return c;
    }

    int main()
    {
        long long n, c;
        cin >> n;
        c = gen(n);
        for (long long i = 0; i < c; i++)
            printf("%lld", prime[i]);
        cout << endl << c;
        return 0;
    }

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/24/