题目描述

把一个偶数拆成两个不同素数的和，有几种拆法呢？

输入

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。

输出

对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

样例输入

30
26
0

样例输出

3
2


 1 #include<stdio.h>
 2 #include<math.h>
 3 
 4 int isPrime(int a)
 5 {
 6     int i;
 7     int flag=1;
 8     //时间超限70%
 9     // for(i=2;i<a;i++){
10     //     if(a%i==0)
11     //         flag=0;
12     // }
13     
14     for(i=2;i<=sqrt(a);i++){
15         if(a%i==0)
16             flag=0;
17     }
18     return flag;            //flag=1:是素数，flag=0:不是素数
19 }
20 
21 int main(){
22     int n;
23     while(scanf("%d",&n)){
24         if(n==0)
25             break;
26         int count=0;
27         int a,b;        //n被拆分成的两个数
28         for(int a=2;a<n/2;a++){
29             b=n-a;
30             if(isPrime(a)&&isPrime(b)){
31                 count++;
32             }
33         }
34         printf("%d\n",count);
35     }
36     return 0;
37 }

solution：

1 求素数的方法们：

　　法一：时间复杂度：o（n）

　　　　　　时间容易超限

　　　　　　for(i=2;i<a;i++){
　　　　　　　　if(a%i==0)
　　　　　　　　flag=0;
　　　　　　　　}
　　法二：时间复杂度O(n*sqrt(n))
　　　　   如果一个数不是素数，则必定为非1和其本身两个数的乘积，其中：较小数<=sqrt（a）；较大数>=sqrt（a），且只需要枚举较小的范围
　　　　　注意：取等～（3*3的情况）
　　　　　　

　　　　for(i=2;i<=sqrt(a);i++){
　　　　　　if(a%i==0)
　　　　　　flag=0;
　　　　　　}

原文地址：http://www.cnblogs.com/luoxiaoluo/p/16870887.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性