亿以内所有素数（Go语言版）

浏览数：28 / 时间：2015年06月10日

了解初等数论的人知道一个判定素数的简易方法：

设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验证知，结果正确。