基础算法——素数的素数筛

2020-10-25 | Share to Twitter

给定一个区间m-n; 求区间内的素数

#include <bits/stdc++.h>

using namespace std;

int isprime(int n);

const int qwq = 1e8;

int a[qwq+1];

int main()
{
    // 0 for prime and 1 for non-prime
    int qaq = sqrt(qwq+1);
    for(int i=0; i<qaq; i++)
    {
        if(a[i]) continue;
        if(isprime(i)) 
            for(int j=i+i; j<qwq; j+=i)
            {
                if(a[j]) break;
                a[j] = 1;
            }
    }
    int m,n; scanf("%d %d", &m, &n);
    for(int i=m; i<n; i++)
        if(!a[i]&&i!=1&&i!=0) printf("%d ", i);
    return 0;
}

int isprime(int n)
{
    if(n==0||n==1) return 0;
    int sn = sqrt(n);
    for (int i = 2; i<sn; i++)
        if (n%i==0) return 0;
    return 1;
}