函数递归查找孪生素数

Question

如何查找孪生素数
孪生素数是指差为 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;
}

Answer 1

 
 
#include<iostream>
using namespace std;
bool f(int n)                // 判断n是否为素数，若是返回真，若不是返回假
{
    if(n<2)return false;
    //**********begin**********
    for(int i = 2; i < n / 2; i++)
        if (n % i == 0) return false;
    return true;
    //**********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函数
    for (i = t + 2; i <= n2; i++)
    {
        if (f(i))
        {
            if (t == i - 2) cout << "(" << t << "," << i << ")" << endl;
            t = i;
        }
    }
    //**********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;
}