了解初等数论的人知道一个判定素数的简易方法:
设n>1为整数,m为整数,且n≤m<n^2,如果小于n的所有素数都不是m的因子,则m为素数。
由此命题,可以编写一个十分简短的遍历亿以内所有素数的程序。
package main
import (
"fmt"
)
var _Primes []uint64 = []uint64{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97,
}
var _N int
func main() {
_CalcPrimes()
fmt.Println(_Primes)
fmt.Println(100000000, "以内的素数个数为", _N)
}
func _CalcPrimes() {
N := len(_Primes)
i := 0
for n := uint64(101); n < 10000; n += 2 {
for i = 1; i < N; i++ { // i从1开始,因为2必然不整除n
if n%_Primes[i] == 0 {
break
}
}
if i == N {
_Primes = append(_Primes, n)
}
}
N = len(_Primes)
for n := uint64(10001); n < 100000000; n += 2 {
for i = 1; i < N; i++ {
if n%_Primes[i] == 0 {
break
}
}
if i == N {
_Primes = append(_Primes, n)
}
}
N = len(_Primes)
_N = N
}
程序的思路极为简单。先列出100以内所有素数,利用这25个素数得到万以内所有素数,并且每得到一个素数,就把它加到_Primes的后面,然后就得到亿以内的所有素数。
由于数组过大,我的计算机无法完全显示。但个数是没有问题的。是5761455。
通过数学软件mathematica验证知,结果正确。