亿以内所有素数(Go语言版)

独立风华 · · 2986 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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














有疑问加站长微信联系(非本文作者)

本文来自:开源中国博客

感谢作者:独立风华

查看原文:亿以内所有素数(Go语言版)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

2986 次点击  
加入收藏 微博
5 回复  |  直到 2000-01-01 00:00:00
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传