hdu2098分拆素数和(素数+暴力)

分拆素数和

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 48614    Accepted Submission(s): 21227

Problem Description

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

 

Input

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

 

Output

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

 

Sample Input

30

26

 

Sample Output

3

2

题意：给出一个偶数，问把这个偶数拆成两个不同素数相加和，有多少种方法。

题解：把偶数前面的素数都算出来保存在数组里，之后每种可能都试一下。

 #include<bits/stdc++.h>
 using namespace std;
 int n;
 int a[];
 int num;
 int isPrime(int n)
 {    //返回1表示判断为质数，0为非质数，在此没有进行输入异常检测
     double n_sqrt;
     if(n== || n==) return ;
     if(n%!= && n%!=) return ;
     n_sqrt=floor(sqrt((double)n));
     for(int i=;i<=n_sqrt;i+=)
     {
         if(n%(i)== | n%(i+)==) return ;
     }
         return ;
 }
 void prime()
 {
     num=;
     for(int i=;i<=n;i++)
     {
         if(isPrime(i))
         {
             a[num++]=i;
         }
     }
 }
 int main()
 {

     while(~scanf("%d",&n),n)
     {
         memset(a,,sizeof(a));
         prime();int ans=;
         for(int i=;i<num;i++)
         {
             for(int j=i+;j<num;j++)
             {
                 if(a[i]+a[j]==n)
                 {
                     //printf("%d %d\n",a[i],a[j]);
                     ans++;
                 }
             }
         }
         printf("%d\n",ans);
     }
     return ;
 }