大家安安 o'_'o

先前已有不少大大分享過建表的部分，我就不贅述了

不知道各位如何儲存質數表？我 4 比較偏好使用 modern c++ 的 STL 提供的容器

不同的容器有不同特性，適應不同的問題

1. vector

Killed

除了 string 以外，最廣為人知的容器大概是 vector，但是直接 TLE QQ

畢竟 vector 插入元素複雜度是線性的

2. set

Accept

好像還可以

3.  set + vector

Accept

快兩倍記憶體的代價，只值 0.1 秒

供您參考

推廣一下我寫的主題：Dark ZeroJudge >///<

謝謝大家

Killed

Accept

Accept

#include<bits/stdc++.h>
using namespace std;
int Input() {  
register char cha;  
register unsigned int x = 0;  
while(cha = getchar())  
if(cha != ' ' && cha != '\n' || cha == EOF) break;  
if(cha == EOF) return -1; 
x = cha-48;  
while(cha = getchar()) {  
if(cha == ' ' || cha == '\n') break;  
x=x*10+cha-48;  
}  
return x;  
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
int a[4792],b=1;
a[0]={2};
for(int c=3;b<4791;c++){
int e=0;
for(int d=0;a[d]<=sqrt(c);d++)
if(c%a[d]==0){
e=1;
break;
}
if(e==0){
a[b]=c;
b++;
}
}
int d;
while(1){
d=Input();
if(d==-1)
break;
int f=0;
for(int e=0;e<4792;e++){
if(a[e]==0||d==a[e])
break;
else if(d%a[e]==0||a[e]>d){
f=1;
break;
}
}
if(f)
cout<<"非質數"<<'\n';
else
cout<<"質數"<<'\n'; 
}
}

輸入優化加建表

使用int當容器

Killed

Accept

Accept

#include<bits/stdc++.h>
using namespace std;
int Input() {  
register char cha;  
register unsigned int x = 0;  
while(cha = getchar())  
if(cha != ' ' && cha != '\n' || cha == EOF) break;  
if(cha == EOF) return -1; 
x = cha-48;  
while(cha = getchar()) {  
if(cha == ' ' || cha == '\n') break;  
x=x*10+cha-48;  
}  
return x;  
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
int a[4792],b=1;
a[0]={2};
for(int c=3;b<4791;c++){
int e=0;
for(int d=0;a[d]<=sqrt(c);d++)
if(c%a[d]==0){
e=1;
break;
}
if(e==0){
a[b]=c;
b++;
}
}
int d;
while(1){
d=Input();
if(d==-1)
break;
int f=0;
for(int e=0;e<4792;e++){
if(a[e]==0||d==a[e])
break;
else if(d%a[e]==0||a[e]>d){
f=1;
break;
}
}
if(f)
cout<<"非質數"<<'\n';
else
cout<<"質數"<<'\n'; 
}
}

我相信樓主的意思是要比較STL容器的速度
int當然比較快啦
不過這題真的要做得快,可以用其他方法:

1.I/O優化其實可以做到0.7s

2.費馬小定理:0.3s(測資裡只有一個卡邁克爾數,手動輸出即可)

3.Miller Rabin Algorithm(推薦使用,大家可以去google一下):96ms

Killed

Accept

Accept

#include<bits/stdc++.h>
using namespace std;
int Input() {  
register char cha;  
register unsigned int x = 0;  
while(cha = getchar())  
if(cha != ' ' && cha != '\n' || cha == EOF) break;  
if(cha == EOF) return -1; 
x = cha-48;  
while(cha = getchar()) {  
if(cha == ' ' || cha == '\n') break;  
x=x*10+cha-48;  
}  
return x;  
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
int a[4792],b=1;
a[0]={2};
for(int c=3;b<4791;c++){
int e=0;
for(int d=0;a[d]<=sqrt(c);d++)
if(c%a[d]==0){
e=1;
break;
}
if(e==0){
a[b]=c;
b++;
}
}
int d;
while(1){
d=Input();
if(d==-1)
break;
int f=0;
for(int e=0;e<4792;e++){
if(a[e]==0||d==a[e])
break;
else if(d%a[e]==0||a[e]>d){
f=1;
break;
}
}
if(f)
cout<<"非質數"<<'\n';
else
cout<<"質數"<<'\n'; 
}
}

#include<cstdio>

using namespace std;

int Input() {  

register char cha;  

register unsigned int x = 0;  

while(cha = getchar())  

if(cha != ' ' && cha != '\n' || cha == EOF) break;  

if(cha == EOF) return -1; 

x = cha-48;  

while(cha = getchar()) {  

if(cha == ' ' || cha == '\n') break;  

x=x*10+cha-48;  

}  

return x;  

}

int main(int argc, char** argv) {

int a[4792],b=1;

a[0]={2};

for(int c=3;b<4791;c++){

int e=0;

for(int d=0;a[d]*a[d]<=c;d++)

if(c%a[d]==0){

e=1;

break;

}

if(e==0){

a[b]=c;

b++;

}

}

int d;

while(1){

d=Input();

if(d==-1)

break;

int f=0;

for(register int e=0;e<4792;e++){

if(a[e]==0||d==a[e])

break;

else if(d%a[e]==0||a[e]>d){

f=1;

break;

}

}

if(f)

printf("非質數\n");

else

printf("質數\n");

}

}

嘗試加速但....

變慢

但也減掃記憶體XD

AC (0.9s, 72KB)