线性筛素数 get！

A4paper · 2018-05-18 23:14:35 · 个人记录

传送门

关键在于

i % prime[ j ] == 0

这句话的理解。

因为 i 是 prime[ j ] 的整数倍，

所以 i * prime[ j+1 ] 就可以用

prime[ j ] * prime[ j+1 ] 的 x 倍来表示。

所以 break 掉就好了。

#include <stdio.h> 
#include <iostream>   
using namespace std;

int prime[10000005],len;
int a[10000005];

void Sieve_Primes(int R)
{
    a[0] = a[1] = 1;
    for(int i=2;i<=R;i++)
    {
        if(a[i] == 0)   prime[++len] = i;
        for(int j=1;j<=len && i*prime[j]<=R;j++)
        {
            a[i*prime[j]] = 1;
            if(i%prime[j] == 0) break;
        }
    }
}

int main()
{
int n,m;
    cin >> n >> m;
    Sieve_Primes(n);
    for(int i=1;i<=m;i++)
    {
int num;
        cin >> num;
        if(a[num] == 1) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}