素数求和

无名侠

嘿嘿，这个暑假我要多多刷题。
原题地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=22
难点：判断一个数时候为素数。
质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。

这里用循环取余的方法。

1. bool isPrime(int x)
   
2. {
   
3.         if (x<=1) return false;
   
4.         for(int i=2;i<x;i++)
   
5.                 if (x%i==0)
   
6.                         return false;
   
7.         return true;
   
8. }

复制代码

完整代码：

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdlib.h>
   
4. bool isPrime(int x)
   
5. {
   
6.         if (x<=1) return false;
   
7.         for(int i=2;i<x;i++)
   
8.                 if (x%i==0)
   
9.                         return false;
   
10.         return true;
    
11. }
    
12. char *mystrlen(char *s)
    
13. {
    
14.         int x=0;
    
15.         while (*s!=' ')
    
16.         {
    
17.                 if(*s=='\0') return s;
    
18.                 x++;
    
19.                 s++;
    
20.         }
    
21.         return (char *)(unsigned int)s+(unsigned int)x;
    
22. }
    
23. int main()
    
24. {
    
25.         int n;
    
26.         int *reason;
    
27.         scanf("%d",&n);
    
28.         reason = new int[n];
    
29.         for (int i=0;i<n;i++)
    
30.         {
    
31.                 int n2;
    
32.                 int Nums[10000];
    
33.                 int sum1=0;
    
34.                 scanf("%d",&n2);
    
35.                 for (int j=0;j<n2;j++)
    
36.                 {
    
37.                         scanf("%d",&Nums[j]);
    
38.                         if (isPrime(Nums[j]))
    
39.                                 sum1+=Nums[j];
    
40.                 }
    
41.                 reason[i] = sum1;
    
42.         }
    
43.         for (int i=0;i<n;i++)
    
44.                 printf("%d\n",reason[i]);
    
45.         return 0;
    
46. }

复制代码

牡丹花下死做鬼

←_← 你这样效率太低了点吧

牡丹花下死做鬼

首先比如取余 是16 你到 根号16 就好了 大于死的根本不用试了

牡丹花下死做鬼

其次 比如 4 可以 2肯定行

牡丹花下死做鬼

也就是说已知的和数也不需要

牡丹花下死做鬼

简单点的思路 先2 看是不是和数 是就不管

牡丹花下死做鬼

不是就从3开始每次2+就好这样至少不会是偶数
当然你还可以没求出一个素数就放到数组里下次就直接用数组里的素数来取余就好

牡丹花下死做鬼

这样效率会高好多
当然还有筛法等等 ~~~  你这个效率真心低