NYOJ 22-素数求和问题

时间限制:3000 ms | 内存限制:65535 KB | 难度:2

描述

现在给你$N$个数$(0<N<1000)$,现在要求你写出一个程序,找出这$N$个数中的所有素数,并求和。

输入

第一行给出整数$M(0<M<10)$代表多少组测试数据
每组测试数据第一行给你$N$,代表该组测试数据的数量。
接下来的$N$个数为要测试的数据,每个数小于$1000$

输出

每组测试数据结果占一行,输出给出的测试数据的所有素数和

样例输入

3
5
1 2 3 4 5
8
11 12 13 14 15 16 17 18
10
21 22 23 24 25 26 27 28 29 30

样例输出

10
41
52

题目来源

http://acm.nyist.net/JudgeOnline/problem.php?pid=22

方法一:枚举法

在一般领域,对正整数$n$,如果用$2$到$\sqrt{n}$之间的所有整数去除,均无法整除,则$n$为质数。
质数大于等于2 不能被它本身和1以外的数整除.

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
#include <iostream>
using namespace std;

bool isPrime(int n){
if(n <= 3){
return n>1;
}else if(n%2==0|| n%3==0){
return false;
}else{
for(int i=5; i*i<=n; i+=6){
if (n%i==0|| n%(i+2)==0) return false;
}
return true;
}
}

int main(){
int a,b,c,d;
cin>>a;
while(a--){
cin>>b;d=0;
while(b--){
cin>>c;
if(isPrime(c)) d=d+c;
}
cout<<d<<endl;
}
}

方法二:Miller-Rabin测试

Miller-Rabin测试:要测试$N$是否为素数,首先将$N-1$分解为$2^Sd$。在每次测试开始时,先随机选一个介于$[1,N-1]$的整数$a$,如果对所有的$r∈[0,s-1]$都满足$a^dmod{N}≠1$且$a^dmod{N}≠-1$,则$N$是合数。否则,$N$有$3/4$的几率为素数。为了提高测试的正确性,可以选择不同的$a$进行多次测试。

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
#include <iostream>
using namespace std;

long long pow_mod(long long a,long long i,long long n){// 快速幂
if(i==0) return 1%n;
int temp = pow_mod(a,i>>1,n);
temp = temp*temp%n;
if(i&1) temp = (long long)temp*a%n;
return temp;
}
bool test(int n,int a,int d){
if(n==2) return true;
if(n==a) return true;
if((n&1)==0) return false;
while(!(d&1)) d=d>>1;
int t = pow_mod(a,d,n);
while((d!=n-1)&&(t!=1)&&(t!=n-1)){
t = (long long)t*t%n;
d = d<<1;
}
return (t==n-1 || (d&1)==1);
}
bool isPrime(int n){
if(n<2) return false;
int a[] = {2,3,61};// 测试集,更广的测试范围需要更大的测试集
for(int i=0; i<=2; ++i)
if(!test(n,a[i],n-1)) return false;
return true;
}

int main(){
int a,b,c,d;
cin>>a;
while(a--){
cin>>b;d=0;
while(b--){
cin>>c;
if(isPrime(c)) d=d+c;
}
cout<<d<<endl;
}
}

参考资料

质数_百度百科
ACM国际大学生程序设计竞赛:算法与实现

文章目录
  1. 1. 方法一:枚举法
  2. 2. 方法二:Miller-Rabin测试
  3. 3. 参考资料

20160315-acm-3/

本页二维码