分拆素数和

源题:Problem - 2098

问题描述:把一个偶数拆成两个不同素数的和,有几种拆法呢?

输入:输入包含一些正的偶数,其值不会超过10000,个数不会超过500,若遇0,则结束。
输出:对应每个偶数,输出其拆成不同素数的个数,每个结果占一行。

样本输入:30

                  26

                  0

样本输出:3

                  2

思路:

将输入的数用循环分为每一组加起来能够与原数相等的两个数(比如输入30,则可以分为1+29,2+28,……)并判断每一组的两个数是否同时为素数,如果是,则可拆法数(即将输出的值)加一;

这里用sqrt()来找素数比较快(因为一个数由两个数相乘时,两个数中小的那个数肯定小于乘后的数的开方值(eg:30=5*6,5*5<30<6*6;63=7*9;7*7<63<9*9)......... ),这样代码就不会超时(The Time Exceeded)......,如果不用答案也会正确,但会超时。

代码:

#include<stdio.h>

#include<math.h>

int su(int x)

{

    int i,j=0;

    for(i=2;i<=sqrt(x);i++)

    {

        if(x%i==0)j++;

    }

    if(j==0)return 1;

    else return 0;

}

main()

{

    int a;

    while(scanf("%d",&a)!=EOF&&a)

    {

        int i,m,n,count=0;

        for(i=2;i<a/2;i++)

        {

          m=su(i);

          n=su(a-i);

          if(m&&n)count++;

        }

        printf("%d\n",count);

    }

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容