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;
}