Code 備忘錄►Math

TOJ::質數判斷

突然發現我對基礎的質數建表非常不熟悉，以下兩種方法，因為第二筆詢問數太多範圍又比較小，所以直接建表；第一筆則是建表到根號N，在用除法判斷，在篩質數時，要注意迴圈的範圍，其實這裡沒什麼大問題，就是如何簡化code和速度而已。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//第一筆  建表到根號N，每筆詢問試除
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 46342
using namespace std;
bool S[N]={0};
int ST[46342],st=0;
int main(int argc,char *argv[])
{
    S[0]=S[1]=1;
    for(int i=2;i<N;i++){
            if(!S[i]){
                      ST[st++]=i;
                      if(i<216)for(int j=i*i;j<=N;j+=i)S[j]=1;
            }
    }
    int t,a;
    scanf("%d",&t);
    while(t--){
               scanf("%d",&a);
               if(a<=N){
                       if(S[a])puts("no");
                       else puts("yes");
               }
               else{
                       for(int i=0;i<ST[i]*ST[i]<=a&&i<st;i++){
                               if(a%ST[i]==0)goto no;
                       }
                       puts("yes");
                       continue;
                       no:;
                       puts("no");
               }
    }
    return 0;
}
//第二筆，直接建表到N，O(1)查詢
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 10000001 
using namespace std;
bool S[N]={0};
int main(int argc,char *argv[])
{
    S[0]=S[1]=1;
    for(int i=2;i<N;i++){
            if(!S[i]){
                      if(i<4000)for(int j=i*i;j<N;j+=i)S[j]=1;
            }
    }
    int t,a;
    scanf("%d",&t);
    while(t--){
               scanf("%d",&a);
               if(S[a])puts("no");
               else puts("yes");
    }
    return 0;
}