写一个可测定不超过1,000,000的素数判定程序
定理:设n是一个正整数,如果对所有的素数p≤根号N,都有płn,则n一定是素数。注:古希腊数学家埃拉托斯散(Eratosthenes,公元前275—公元前194)发明了求比某给定数小的素数的筛法技巧。
方法如下:
对于任意给定的正整数N,要求出所有不超过N的素数。我们列出N个整数,从中删除小于等于根号N的所有素数p1,…,pk的倍数。然后依次删除,
p1的倍数:2p1,…, p1
……
pk的倍数:2pk,…, pk
余下的整数(不包括1)就是所要求的不超过N的素数。