最简素数算法

最简素数算法
昨天教女友vb，无聊就自己写了个素数算法的程序，今天又用perl写了遍。

从算法复杂性（速度）来说这个算法应该是最快的了，不过有个缺点是算一个素数要依赖之前的素数。

比如说我测试101是不是素数，一般算法是用101除于小于101的开方数2.. 9，那样就进行了9次运算，或者之前的奇数3 5 7 9四个数，但假如用10以前的素数算的话，只用3次运算3 5 7(9是素数)。而且随着数字增大素数会越来越少，比如算10001，传统算法要算3～99的奇数运算49次，而我的算法只要运算24次就行了（100前有25个素数，而且2不用代入运算了）。

我linux+1.5G CPU今天算了4个钟（中间出去打球了），算到9位数14开头的吧，而且继续算下去的速度还好快。我都怀疑print是不是占时间太多。

我觉得再换成指针来计算更快吧。希望大家可以提出写什么建议再优化这个程序，算法本身我觉得改进不了的了。

还有……，传不了附件……

#!/usr/bin/perl -w
# a perl script to calculate the prime number
# by 1e0n 050410
# thinks:my love Cathy

use strict;

my (@prime,$num,$prime_flag,$if_prime,$prime_last);
@prime = 1..3; #set prime[0]=1(not use),prime[1]=2,prime[3]=3.
$prime_flag = 1;
$prime_last = 2;

for (2..1000) { #u can change it to 999...999 ^_^
$num = 2 * $_ + 1;
$if_prime = 1;

if ($prime[$prime_flag+1] * $prime[$prime_flag+1] == $num) {
$prime_flag++;
print $prime_last." ".$prime_flag." ".$prime[$prime_flag]." ".$num."\n";
next; #so $num already is not a prime,just go next
}

for (1..$prime_flag) {
if ($num % $prime[$_] == 0) {
$if_prime = 0;
last;
}
}

if ($if_prime) {
$prime[++$prime_last] = $num;
#print $prime_last." ".$num."\n";
}
}

#print "@prime"."\n";

sorry，之前是<...
sorry，之前是
#print $prime_last." ".$prime_flag." ".$prime[$prime_flag]." ".$num."\n";
print $prime_last." ".$num."\n";

而不是
print $prime_last." ".$prime_flag." ".$prime[$prime_flag]." ".$num."\n";
#print $prime_last." ".$num."\n";
的

这样才能打印出所有素数来。

你的算法不是最...
你的算法不是最快！

例如：Ｎ=２^１２７-１是一个３８位数，要验证它是否为素数，有下面几个不同的方法：
1.遍历２以上Ｎ的平方根以下的每一个整数，是不是能整除Ｎ;(这是最基本的方法）
2.遍历２以上Ｎ的平方根以下的每一个素数，是不是能整除Ｎ;(这个方法是上面方法的改进，但要求N平方根以下的素数已全部知道)
3.采用Rabin-Miller算法进行验算；
验算结果，假设计算机能每秒钟计算１亿次除法，那么
算法１要用４１３６年，算法２要用９３年，算法３只要不到１秒钟！

另外印度好像有人宣称素数测试是P问题，我有那篇论文，但看不懂：（

   

这个我知道，好...
这个我知道，好像只用9步的判断（非循环，是顺序型的）就可以求出个数是不是素数了。
就是算法复杂度是n(1)?~

我上网搜过这个算法，不过看不懂……

可能有O(1)的算...
可能有O(1)的算法吗？？至少Rabin-Miller算法不是O(1)
[quote]
#include<cstdio>
#include<cstdlib>
#include<cmath>

bool Witness(int a,int n)
{
int i,d=1,x;
for (i=(int)ceil(log((double)n-1)/log(2.0))-1;i>=0;--i) {
x=d;
d=(d*d)%n;
if ((1==d) && (x!=1) && (x!=n-1)) return 1;
if (((n-1)&(1<<i))>0) d=(d*a)%n;
}
return (d!=1);
}

bool Rabin_Miller(int n,int s)
{
int j,a;
for (j=0;j<s;++j) {
a=rand()*(n-2)/RAND_MAX+1;
if (Witness(a,n)) return false;
}
return true;
}

int main()
{
int i;
for (i=3;;i+=2) if (Rabin_Miller(i,20)) printf("%d\n",i);
/* 这里第二个参数取20，能够保证出错概率小于2^(-20)，也可以改的更大使得出错概率更小。 */
return 0;
}
[/quote]

   

http://lijh.bj...
http://lijh.bj4hs.edu.cn/newmath.htm

素数判定新方法的启示

日前，印度的三位计算机专家震惊了数学界，他们不但为古老的素数判定问题找到了答案，而且令人始料未及的是，他们的判定方法出奇地简单，简单到足以让数学家们警觉起来，启发他们重新审视许多复杂问题的解决方法。
作为除了1和自身外没有其他约数的正整数，数千年来素数一直是数论的基本构件。对于如何判定一个数是否为素数，公元前240年，希腊数学家埃拉托色尼给出了一个一直沿用到今天的方法――“筛选法”。该方法有其局限性，即随着数字的增大，筛选所耗用的时间呈指数增长。如果要判定相当大的自然数，哪怕采用最先进的计算机进行运算，计算时间比宇宙年龄都要长。因此，长期以来，数学家们一直致力于寻找的，就是在可以接受的时间内能够完成的判定方法。
在过去的几十年间，由于素数判定问题被引入了密码学领域，这方面的研究工作变得倍受关注。因为当前的因特网加密程序，主要是基于大数的素因子分解相当困难这一假定。虽然目前有一些高速程序可以给出一个大数是素数的概率，但它毕竟没有彻底解决问题。
印度理工学院计算机科学与工程学系的科学家马宁德拉?阿格拉瓦和他的两位在校本科生尼拉叶?卡雅尔和尼汀?萨克斯特纳在这方面取得了成功。
这三个人的成功主要得益于采用了崭新的思路。其他人的着眼点往往是“这个数是否是素数”，他们却另辟蹊径，将问题转化成关于待判定数的一系列小的问题或 “方程”。于是，简单的算法诞生了，只需用13行便可写明。阿格拉瓦解释说：“如果某个数字使所有等式成立，那么它就是素数；否则，便不是。”
卡尔?波默朗斯是美国新泽西州贝尔实验室的素数问题专家，他评论说：“这是一个漂亮的算法，我为之高兴。同时，也很遗憾自己没找到它。他们的方法很简洁，但并不平凡。他们的工作充满智慧。”
英国沃里克大学的数学家和科普作家伊恩?斯图亚特认为，这一理论突破就其本身而言固然重要，但它给人们思路上带来的启发意义更加深远。如果采用它所蕴含的换个角度、化繁为简的思想，对于那些目前处在死胡同中的难题，科学家们也许可以找到解决办法。
因特网安全目前还未因此受到威胁。来自英国一个加密安全公司的本?哈德利说：“相对于原来的概率计算算法，新算法并没有给素因子分解提供好的算法，所以这一新突破对密码安全行业并没有太大的实际影响。”
但是，波默朗斯坚信新算法将使密码学专家担忧。他认为，既然存在简单的素数判定算法，也就很可能存在简单的素因子分解算法，只是我们还没注意到罢了。
这恐怕也正是阿格拉瓦等人研究工作的真正意义所在。两名本科生的毕业项目能产生如此重大的成果，这说明我们很可能忽略掉了更多重大数学问题的简单解答方法。波默朗斯感慨颇深地说：“这是一个提醒，原来我们非常容易忽略掉一些简单的东西。”

----每个合...


每个合数都可以由质数相乘组成。例如15=3*5
可以把待检验的数用前面找到的质数相除。
用于检验的质数不超过该数的平方根就可以了