Firefly 
1025 words
5 minutes
Go语言教程：使用爱拉托逊斯筛选法获取质数
在本教程中，我们将深入探讨如何使用Go语言编写一个程序来获取小于或等于给定数值的所有质数。我们将使用爱拉托逊斯筛选法（Sieve of Eratosthenes）来实现这一目标，并通过单元测试和基准测试来验证和评估我们的实现。
1. 什么是质数？
质数是大于1的自然数，且只能被1和它本身整除。例如，2、3、5、7等都是质数。
2. 爱拉托逊斯筛选法简介
爱拉托逊斯筛选法是一种高效的算法，用于找出一定范围内的所有质数。其基本思想是：
- 创建一个从2到最大数的列表。
- 从列表中选择第一个未标记的数（初始为2），将其所有倍数标记为非质数。
- 重复步骤2，直到处理到最大数的平方根为止。
- 剩下未标记的数即为质数。
3. 实现代码
我们将分为两个部分：质数生成函数和测试代码。
3.1 质数生成函数
package q1
import ( "math")
// GetPrimes 用于获取小于或等于参数max的所有质数。// 本函数使用的是爱拉托逊斯筛选法（Sieve Of Eratosthenes）。func GetPrimes(max int) []int { if max <= 1 { return []int{} } marks := make([]bool, max) var count int squareRoot := int(math.Sqrt(float64(max))) for i := 2; i <= squareRoot; i++ { if marks[i] == false { for j := i * i; j < max; j += i { if marks[j] == false { marks[j] = true count++ } } } } primes := make([]int, 0, max-count) for i := 2; i < max; i++ { if marks[i] == false { primes = append(primes, i) } } return primes}3.2 测试代码
package q1
import ( "testing")
var expectedPrimes = []int{ 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,}
func TestGetPrimesWith1000(t *testing.T) { max := 1000 primes := GetPrimes(max) for i, prime := range primes { expectedPrime := expectedPrimes[i] if prime != expectedPrime { t.Errorf("%dth prime number %d is not the expected value %d", i, prime, expectedPrime) } } if t.Failed() == false { t.Logf("The primes less than %d are all correct.", max) }}
func BenchmarkGetPrimesWith100(b *testing.B) { for i := 0; i < b.N; i++ { GetPrimes(100) }}
func BenchmarkGetPrimesWith10000(b *testing.B) { for i := 0; i < b.N; i++ { GetPrimes(10000) }}
func BenchmarkGetPrimesWith1000000(b *testing.B) { for i := 0; i < b.N; i++ { GetPrimes(1000000) }}4. 代码解析
4.1 GetPrimes函数
- 输入参数：
max，表示要找出小于或等于该值的所有质数。 - 返回值：一个包含所有质数的切片。
步骤解析：
- 边界检查：如果
max小于等于1，直接返回空切片。 - 初始化标记数组：创建一个布尔数组
marks，长度为max，用于标记非质数。 - 筛选质数：
- 计算
max的平方根squareRoot。 - 从2开始遍历到
squareRoot，如果当前数未被标记为非质数，则将其所有倍数标记为非质数。
- 计算
- 收集质数：遍历
marks数组，将未被标记的数收集到primes切片中。
4.2 测试函数
TestGetPrimesWith1000：测试GetPrimes函数是否能正确找出小于1000的所有质数。- 基准测试：通过
Benchmark函数测试GetPrimes函数在不同输入规模下的性能。
5. 运行测试
在终端中运行以下命令来执行测试和基准测试：
go test -vgo test -bench=.6. 总结
通过本教程，我们学习了如何使用Go语言实现爱拉托逊斯筛选法来找出质数，并通过单元测试和基准测试验证和评估我们的实现。希望通过这个例子，您能更好地理解Go语言的基本语法和测试方法。
Share
If this article helped you, please share it with others!
Go语言教程：使用爱拉托逊斯筛选法获取质数
https://blog.ithuo.net/posts/go-tutorial-sieve-of-eratosthenes-prime-numbers/ Last updated on 2022-05-22，1347 days ago
Some content may be outdated