循环～分拆素数和

标签：拆成 int sqrt 偶数 素数 循环 分拆 include

题目描述

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

输入

输入包含一些正的偶数，其值不会超过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; 　　　　　　}

标签：拆成,int,sqrt,偶数,素数,循环,分拆,include
From： https://www.cnblogs.com/luoxiaoluo/p/16870887.html