当前位置:首页 > 尘凡 > 正文内容

解求素数

满纸空言11个月前 (08-22)尘凡30810

不过哪种方法,数越大越耗时,甚至导致goland崩溃。

为了减少计算,只将素数组作为取余因子

package main

import (
	"fmt"
)

func main() {
	primeArray := []int{2}
	for num := 2; num <= 10000; num++ {
		isPrime := true
		for _, i := range primeArray {
			if num%i == 0 {
				isPrime = false
				break
			}
		}
		if isPrime {
			primeArray = append(primeArray, num)
		}
	}
	fmt.Println(primeArray)
}

筛选法:

package main

import (
	"fmt"
	"math"
)

func sieveOfEratosthenes(n int) []int {
	isPrime := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		isPrime[i] = true
	}

	for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
		if isPrime[i] {
			for j := i * i; j <= n; j += i {
				isPrime[j] = false
			}
		}
	}

	primes := []int{}
	for i := 2; i <= n; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}

	return primes
}

func main() {
	primes := sieveOfEratosthenes(1000000000)

	for _, prime := range primes {
		fmt.Println(prime)
	}
}

 

扫描二维码推送至手机访问。

版权声明:本文由满纸空言发布,如需转载请注明出处。

本文链接:https://mzky.cc/post/141.html

分享给朋友:

“解求素数” 的相关文章

golang的os包使用备忘3年前 (2021-04-21)
njmon参数3年前 (2021-04-21)
CSRF漏洞修复3年前 (2021-06-10)
go语言优秀的框架3年前 (2021-07-19)

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。