題目描述
- 給定一個(gè)正整數(shù)羽峰，編寫程序計(jì)算有多少對(duì)質(zhì)數(shù)的和等于輸入的這個(gè)正整數(shù)踊赠，并輸出結(jié)果。輸入值小于1000电湘。
如隔节，輸入為10, 程序應(yīng)該輸出結(jié)果為2万搔。（共有兩對(duì)質(zhì)數(shù)的和為10,分別為(5,5),(3,7)）*
思路描述
這個(gè)問題比較重要的點(diǎn)在于如何判斷一個(gè)數(shù)是否是素?cái)?shù)
如何判斷一個(gè)數(shù)是否是素?cái)?shù)呢？
第一種方法
設(shè)輸入值為num官帘。
for i=2 to num-1
if(num%i==0)
return false;
return true;
方法一時(shí)間復(fù)雜度為O(n).
第二種方法
for i=2 to sqrt(num)
if(num%i==0)
return false;
return true;
時(shí)間復(fù)雜度為O(log2N)
最后給出代碼如下瞬雹，由于沒有找到原文出處，對(duì)原作者表示歉意刽虹，侵刪酗捌。
#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;
}
這個(gè)方法比較難以想通的是為什么primer函數(shù)中，最后判斷6X兩側(cè)的數(shù)是否是質(zhì)數(shù)涌哲。事實(shí)上通過前兩步的過濾胖缤，數(shù)字空間只剩下了這兩種數(shù)，其他的數(shù)字都被過濾掉了阀圾。因?yàn)橹恍枰袛嘣谶@些數(shù)字就足夠了哪廓。
