题目的大致意思是对于任何一个大于等于4的偶数n,至少存在一对素数p1,p2。使得n=p1+p2,给定一个偶数n,可以分解几对素数之和。n的取值范围为4-32767。
#include<stdio.h> int isPrime(int n){ int i; for(i=2;i*i<=n;i++){ if(n%i==0)return 0; } return 1; } int main(){ int n,i,count; while(scanf("%d",&n)){ count=0; if(n==0)break; for(i=2;i<=n/2;i++){ //如果i为素数并且n-i也为素数,结果加1 if(isPrime(i) && isPrime(n-i)) count++; } printf("%d\n",count); } return 0; }
提交后果断超时。分析题目和程序,题目有多组的输入,对于n需要判断从2至n/2的数是不是素数。对于多组数据上面的程序存在重复判断素数。比如每一次输入10,首先需要判断从2~5之间所有数是否为素数。如果第二组数据输入的是12,需要判断2~6之间的所有数是否为素数。而在第一步组数据中已经判断了2~5之间的数。由此可见,第二次的判断从2~5是重复的判断,当输入的数据超多时,不超时才怪。
再次看了下题目,发现题目中n的范围并不是太多4-32767。既然数据并不是很大,用一个32768大小的数组来记录对应数组下标是否为素数。改进后的程序如下:
#include<stdio.h> int data[32768]; int isPrime(int n){ int i; for(i=2;i*i<=n;i++) if(n%i==0)return 0; return 1; } void cal(){ int i; for(i=2;i<=32767;i++){ if(isPrime(i))data[i]=1;//是素数标记为1 else data[i]=0;//否则标记0 } } int main(){ int n,i,count; cal(); while(scanf("%d",&n)){ count=0; if(n==0)break; for(i=2;i<=n/2;i++){ //i是素并且n-i是素数,结果加1 if(data[i]==1 && data[n-i]==1) count++; } printf("%d\n",count); } return 0; }
再次提交250ms A掉。
一次性将2-32767之间的所有素标记为是否为素数,后面程序只需要根据数组中元素的值判断。通过32768*4字节的内存的“浪费"就可以极大的提高了程序的运行速度。