如何查找孪生素数
孪生素数是指差为 2 的一对素数。查找指定范围内孪生素数的思路是找出指定范围内的第 1 个素数 t ,然后从小到大遍历其他的数,找出下一个素数 i ,找到后执行下列两步操作:
(1)把当前素数 i 和前一个素数(t)比较,若 i-t=2 ,则 t 和 i 是孪生素数,并输出;
(2)用 i 替换 t ,即在找出下一个素数前,把前一步(1)找出的当前素数 i 作为前一个素数 t 。
以此类推,找出指定范围内的所有孪生素数对。
迭代思想
在查找孪生素数的过程中,每找到一个新的素数,在下次查找前,用当前的素数替代前一个素数 ,这就是迭代。这样对于每个整数只要判断一次其是否为素数即可,可提高了程序的运行效率。
编程要求
程序中除主函数外,定义了下列2个函数:
f(n)函数,用于判断n是否为素数,若是返回真,若不是返回假;
fun(n1,n2)函数,用于查找并输出n1、n2之间的孪生素数。
在主函数中定义并输入n1和n2,并使n1<n2,然后调用上述函数,输出n1、n2之间的孪生素数对。
根据算法提示,在右侧编辑器的每对“//begin”和“
//end”之间填写代码,把程序补充完整。
注意,代码中不要使用'\t'或“\t”,而以空格字符‘ ’或字符串“ ”代替'\t'和“\t”。
测试说明
平台会对你编写的代码进行测试:
测试输入:0 50
预期输出:
(3,5)
(5,7)
(11,13)
(17,19)
(29,31)
(41,43)
测试输入:150 50
预期输出:
(59,61)
(71,73)
(101,103)
(107,109)
(137,139)
#include<iostream>
using namespace std;
bool f(int n) // 判断n是否为素数,若是返回真,若不是返回假
{
if(n<2)return false;
//**********begin**********
//**********end**********
}
void fun(int n1,int n2) // 查找并输出n1、n2之间的孪生素数,
{
int i,t;
for(t=n1;t<=n2;t++) // 查找n1、n2之间的第1个素数t
if(f(t))break;
if(t>n2+1) return; // 若n1、n2之间没有素数,则结束函数调用
//**********begin**********查找孪生素数,要求采用迭代的思想,每个数只调用一次f函数
//**********end**********
}
int main(void)
{
int n1,n2,t;
cin>>n1>>n2;
if(n1>n2){ // 使n1<n2
t=n1;
n1=n2;
n2=t;
}
fun(n1,n2);
system("pause");
return 0;
}