S-1106-素数检测 加 素数筛选法求一块区间所有素数

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 
给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。
Input
第1行：一个数N，表示正整数的数量。(1 <= N <= 1000)
第2 - N + 1行：每行1个数(2 <= S[i] <= 10^9)
Output
输出共N行，每行为 Yes 或 No。
Input示例

5
2
3
4
5
6

Output示例

Yes
Yes
No
Yes
No

较暴力算法思路：

（1）从2开始，2是最小的质数。

（2）除了2之外的偶数全都不是质数，因为除了1和自身之外它们还能被2整除。若为大于2的奇数，则进入下一步继续判断。

（3）将其开方，若从3到开方向下取整之间的所有奇数都不能将其整除，则说明该数为质数。

至于为什么只用除到其平方根？

#include<stdio.h>
#include <iostream>
#include<cmath>
using namespace std;
const int maxn=1e9+7;
int ispes(int n){
    if(n<2) return false;
    if(n==2) return true;
    if(n%2 == 0) return false;
    for(int i=3;i*i<=n;i++){
        if(n%i==0)
        return false;
    }
    return true;
}
int main(){
    int num;
    int t;
    cin>>t;
    //FilterPrime();
    while(t--){
        cin>>num;
        if(ispes(num))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

素数筛选法

思路：

我们知道要求某一区间内的素数，只需要将这一区间内的合数去除，即筛除即可，这种办法利用的就是这种思想。

第一遍筛掉2的倍数:剩下2,3,5,7,9,11,13,15.....

第二遍筛掉3的倍数:剩下2,3,5,7,11,13,....

第三遍筛掉5的倍数:(为什么是5而不是4,因为4已经被2的倍数筛掉了，再筛已经无意义)

第四遍筛掉7的倍数:(为什么是7而不是6,同理因为6已经被之前的2,3筛掉了再筛也没有意义了)

以此类推.......................

代码：

#include<iostream>
#include<string>
using namespace std;
const int maxn=50005;
const int N = 50000;
int Prime[maxn]; //保存素数
bool isPrime[maxn];//标记该位是否是素数
int len;
//fin [2,N] 's prime
void SetPrime()
{
    int i,j;
    len = 0;
    for(int i=2;i<=maxn;i++)isPrime[i]=true;
    for(i=2; i<=N; ++i)
    {
        if(isPrime[i])
        {
            Prime[len++] = i;
            for(j=i+i; j<=N; j += i)
                isPrime[j] = false;
        }
    }
}
int main()
{
    SetPrime();
    int i;
    for(i=1; i<len; ++i)
        cout << Prime[i] <<' ';
    cout << endl;
    return 0;
}

优化的线性筛

#include<stdio.h>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e7+7;//求MAX范围内的素数
long long su[MAX],cnt;
bool isprime[MAX];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
    isprime[0]=isprime[1]=0;//0和1不是素数
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;//保存素数i
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
        }
    }
}
int main()
{
    prime();
    //for(long long i=1;i<cnt;i++)
     //   printf("%d  ",su[i]);
    return 0;
}