质数的分布规则--斌语。转

        　质数之遇－－数学归纳法的无奈

先观察下面的一个简单统计表：

1~9之间的质数:2,3,5,7  共4个．

1~25之间的质数:2,3,5,7,11,13,17,19,23.  共9个.

1~49之间的质数:2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.  共15个．

于是，我们可以猜想得出:从1~n² (n为大于1的奇数)里，含有质数的个数为M=(n-1)*(n+13)/8.把它展开，写成一个更通用的多项式，即:m=(n²+12n-13)/8.

为验证此猜想是否正确，我们用数学归纳法证明如下：

1)当n=3时，n²=9.里面的质数为2,3,5,7;共计4个．依公式计算m=( n²+12n-13)/8=(3²+12*3-　　　　　　　　　　　　　　　　　　　　　　          13)/8=4.成立．

2)假设n=k时此式也成立，则当n=k+1时，有

　　　M=(n-1)*(n+13)/8

        =[(k+1)-1][(k+1)+13]/8

        =(k²+14k)/8

        =[(k²+2k+1)+(12k+12)-(12+1)]/8

        =[(K+1)²+12(k+1)-13]/8

即得证．

上面的数学归纳法看起来比较正确，为更一步验证，还要用程序语言把此猜想写出来，进行初步检验．下面是我写的一个统计从1~n之间的质数个数和依据上面公式算得的结果，并将两者作比．程序段如下：

#include <stdio.h>

#include<math.h>

/*int isPrime(int x); */

int isPrime(long x);/*对判断是否为质数的函数声明*/

int m=0;                /*对计数器的声明*/

int main()

{

long i;             

long n;                /*输入值，在此要求n为奇数的平方值*/

long a;                /*依公式算出来的值*/

printf("\nPlease input a number: ");

scanf("%ld", &n);

printf("\n");

printf("\nThe primes are  ");

for(i=2;i<=n;i++)     /*从2到n依次判断是否为质数*/

if(isPrime(i))

{

  printf("%ld ",i);

  m++;                /*统计质数个数*/

}

printf("\nThe number of prime is %d",m);

a=(sqrt(n)-1)*(sqrt(n)+13)/8;

printf("\nThe result of m is %d",a);

if(m!=a)              /*判断从统计的结果与公式的结果是否是相同*/

  printf("\nError out!");

else

  printf("\nverything is ok!");

/*printf("\n%d",m);*/

}

int isPrime(long x) /*这个是判断是否素数的函数，是返回1，不是返回0 */

{

long i;

int flag=1;

for(i=2;i<=sqrt(x);i++)

if(x%i==0)

{

flag=0;

break;

}

return flag;

}

在Turbo C里面运行．但是，当进行到15²（即225）时，出现了偏差．截图如下：