C语言求孪生素数

问题描述

所谓孪生素数指的是间隔为2的两个相邻素数，因为它们之间的距离已经近的不能再近了，如同孪生兄弟一样，所以将这一对素数称为孪生素数。

显然，最小的一对孪生素数是（1，3）。我们可以写出3〜100以内的孪生素数，一共有8对，分别是（3，5），（5，7），（11，13），（17，19），（29，31），（41，43），（59，61）和（71，73）。随着数字的增大，孪生素数的分布也越来越稀疏，人工寻找孪生素数变得非常困难。

本题要解决的问题是：编程求出3〜1000以内的所有孪生素数。

问题分析

孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2称为孪生素数。

要编程求解的问题是找出3〜1000以内的所有孪生素数，因此很自然的可以使用穷举法对3〜1000以内的每一个整数n进行考察，先判断n是否为素数，再判断n+2是否为素数，如果n和n+2同时为素数，则（n，n+2)就是一对孪生素数，将其打印输出即可。

算法设计

在算法设计中需要采用循环结构。

在判断是否为素数时可以定义一个函数prime()，每次判断整数n是否为素数时都将n作为实参传递给函数prime()，在prime()函数中使用前面介绍过的判别素数的方法进行判断。如果n为素数，则primeO函数返回值为1，否则prime()函数返回值为0。

程序流程图：

下面是完整的代码：

#include <stdio.h>
#include <math.h>
int prime(int n)
{
    int j;
    long k;
    k=sqrt(n)+1;
    for(j=2; j<=k; j++)
    {
        if (n%j == 0)
        {
            return 0;  /*n能被j整除，不是素数，返回0*/
        }
    }
    return 1;  /*n是素数，返回1*/
}
int main ()
{
    int i, count=0;
    printf("The twin prime pairs between 3 and 1000 are: \n");
    for (i=3; i<1000; i++)
        if( prime(i) && prime(i+2) )
        {
            printf("(%-3d,%3d)  ", i, i+2);
            count++;
            if(count%5 == 0)  /*变量count控制每行打印的个数，每打印5对孪生素数换行*/
                printf("\n");
        }
   
    return 0;
}

运行结果：