求费尔马二平方素数

贴一段给你：

编程思路�本文拟用c语言编程，求42亿之内的费尔马“二平方”素数。�如果按定义从左向右，先求一个素数F，然后再去找相应的素数X、Y，工作量重复太大。我们可以对上述公式进行分析：

�1、左侧F是素数，它肯定是奇数，那么右侧两式的和也应该是奇数，这样X和Y为一奇一偶，因为奇数的平方还是奇数，偶数的平方还是偶数。X、Y又要求是素数，而既是偶数又是素数的数只有一个，就是2。我们假定X＝2。所以（1）式可以简化为：�F＝2＊2＋Y＊Y（2）�也就是说，费尔马“二平方”素数的表示形式是惟一的。

�2、按式（2）由右向左，由小到大找素数Y，再计算出相应的F，判断其是否素数。

�3、求出素数Y后将其保存起来，在判断其它数是否素数时可直接用已求出的素数去除，如此反复。

�源程序�

#include�

voidmain()

{

unsignedlongi,j,a[10000],m,m1=3,m2=7,b=1,n=0,d=1,x=4000000000;�

a[1]=2;�

10:for(i=m1;i<=m2;i++,i++)�

{

if(i%a[1]==0)goto13;

for(j=2;j<=d-1;j++)�

if(i%a[j]==0)goto13;�

a[b++]=i;m=i*i+4;�

if(m>x)goto14;�

for(j=2;j<=b-2;j++)�

if(m%a[j]==0)goto13;�

printf(%20lu=2*2+%5lu*%5lu,m,i,i);�

if(++n%2==0)printf(\n);�

13:m1=m2+4;m2=a[++d]*a[d]-2;�

goto10;�

14:printf(\ntotal=%lu\n,n);�

}

�结论�

运行程序会发现，除“29＝2＊2＋5＊5”以外，所有的费尔马“二平方”素数个位数字都是3，相应Y的个位数字都是3或7。�费尔马“二平方”素数分布（修改程序中变量x的值得到）也很耐人寻味，请看下表（表中10万以内包含1万以内，下同）：

�范围个数最大的一个的表达式�

1万109413＝2＊2＋97＊97�

10万2097973＝2＊2＋313＊313�

100万42994013＝2＊2＋997＊997�

1000万769223373＝2＊2＋3037＊3037�

1亿18397752773＝2＊2＋9887＊9887�

10亿427999002453＝2＊2＋31607＊31607�

20亿5511983188093＝2＊2＋44533＊44533�

30亿6412993512373＝2＊2＋54713＊54713�

40亿7183977446493＝2＊2＋63067＊63067�

费尔马“二平方”素数太少了，40亿内才718个，千万分之二还不到呢。

�随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？

�费尔马“二平方”素数是无穷多个呢，还是有限多个呢？如果是有限个，又是多少个呢？最大的一个又是什么数呢？

�这些问题的证明可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！�

----------------------------------------------------------------------

下面是作者原程序,因为是中文全角,上面的就改了一下原文放在下面对照:

＃include〃math．h〃�

main（）�

｛unsignedlongi，j，a〔10000〕，m，m1＝3，m2＝7，�b＝1，n＝0，d＝1，x＝4000000000；�

a〔1〕＝2；�

l0：for（i＝m1；i＜＝m2；i＋＋，i＋＋）�

｛if（i％a〔1〕＝＝0）gotol3；�

for（j＝2；j＜＝d－1；j＋＋）�

if（i％a〔j〕＝＝0）gotol3；�

a〔b＋＋〕＝i；m＝i＊i＋4；�

if（m＞x）gotol4；�

for（j＝2；j＜＝b－2；j＋＋）�

if（m％a〔j〕＝＝0）gotol3；�

printf（〃％20lu＝2＊2＋％5lu＊％5lu〃，m，i，i）；�

if（＋＋n％2＝＝0）printf（〃＼n〃）；�

l3：；｝�m1＝m2＋4；m2＝a〔＋＋d〕＊a〔d〕－2；�

gotol0；�

l4：printf（〃＼ntotal＝％lu＼n〃，n）；�

｝

本文来自:乘风原创程序(http://www.qqcf.com)详细出处参考：http://study.qqcf.com/web/173/20276.htm