By yusijia

Updated:

Contents
  1. 1. 素数筛选法

素数筛选法

  • 预处理的时候把表打出来，复杂度：O(nlogn),然后O(1)查询
  • 思路就是从2开始往后把他的整数倍的数做个标记为不是素数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <cstdio>

int mark[1000] = {0};                       //0代表质数

int main()
{
    int n;                                  //预处理
    for(int i = 2; i <= 1000; i++)if(mark[i] == 0){//前面没有因子使mark[i]变成1，说明除了1和本身不能被别的数整除了
        for(int j = i + i; j <= 1000; j += i){//整数倍的移动
            mark[j] = 1;                    //他的整数倍的数都不是素数，因为因子中除了1和本身还多了他
        }

    }
    int a;
    while(scanf("%d",&n)!=EOF)              //要输入的数的个数
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);                 //不能输入1，不是素数，输入1是没有意义的
            printf(mark[a]==0?"Y ":"N ");   //问号冒号表达式  //输入一次判断一次
            /*if(mark[a]==0)                //注意是mark[a] ,查表
                printf("Y ");
            else
                printf("N ");*/
	    printf("\n");
        }
    }
    return 0;
}
//注意：1不是素数，从2开始预处理，
Contents
  1. 1. 素数筛选法