题目描述
- 给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）*
思路描述
这个问题比较重要的点在于如何判断一个数是否是素数
如何判断一个数是否是素数呢？
第一种方法
设输入值为num。
for i=2 to num-1
if(num%i==0)
return false;
return true;
方法一时间复杂度为O(n).
第二种方法
for i=2 to sqrt(num)
if(num%i==0)
return false;
return true;
时间复杂度为O(log2N)
最后给出代码如下，由于没有找到原文出处，对原作者表示歉意，侵删。
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
bool is_Prime(int num)
{
if(num==2||num==3)
return true;
if (num%6!=5&&num%6!=1)
return false;
int num1=sqrt(num);
for(int i=5;i<=num1;i+=6)
{
if(num%i==0||num%(i+2)==0)
return false;
}
return true;
}
int main()
{
int number;
int sum=0;
cin>>number;
for(int i=2;i<=number/2;i++)
{
if(is_Prime(i)&&is_Prime(number-i))
sum++;
}
cout<<sum<<endl;
}
这个方法比较难以想通的是为什么primer函数中，最后判断6X两侧的数是否是质数。事实上通过前两步的过滤，数字空间只剩下了这两种数，其他的数字都被过滤掉了。因为只需要判断在这些数字就足够了。
