Go语言实现筛选法求100以内素数

算法思路

筛选法的核心逻辑是：找出一个非素数就把它“挖掉”（即从数据中移除或标记），最后剩下的就是素数。具体步骤如下：

1. 初始化：创建一个包含1到100数字的数组。
2. 剔除无效项将1标记为非素数（索引为0）。
3. 筛选非素数：从2开始遍历到100的平方根。如果当前数是素数，则将其所有倍数在数组中置为0。
4. 输出结果：遍历数组，打印所有值不为0的元素，并按每行10个进行换行格式化。

代码实现

以下是完整的Go语言实现代码。注意，为了保持代码整洁和安全性，这里使用了标准的 fmt 包进行输入输出，并使用 math.Sqrt 优化循环边界。

package main

import (
	"fmt"
	"math"
)

func main() {
	// 定义变量
	var i, j, n int
	// 定义数组存储1-100，下标对应数值
	var a [101]int

	// 1. 初始化数组，a[i] = i
	for i = 1; i <= 100; i++ {
		a[i] = i
	}

	// 2. 1既不是质数也不是合数，标记为0
	a[1] = 0

	// 3. 筛选法核心逻辑
	// i 从2遍历到 sqrt(100)，即10
	for i = 2; i < int(math.Sqrt(100)); i++ {
		// j 从 i+1 遍历到100
		for j = i + 1; j <= 100; j++ {
			// 如果i和j对应的值都不为0（均为素数候选）
			if (a[i] != 0) && (a[j] != 0) {
				// 如果j能被i整除，说明j是非素数
				if a[j]%a[i] == 0 {
					a[j] = 0 // 将非素数位置标记为0
				}
			}
		}
	}

	// 4. 输出结果
	fmt.Println()
	for i, n = 1, 0; i <= 100; i++ {
		if a[i] != 0 {
			fmt.Print(a[i], "\t")
			n++
		}
		// 每行打印10个数后换行
		if n == 10 {
			fmt.Println()
			n = 0
		}
	}
}

关键点解析

• 数组下标映射：代码中使用长度为101的数组，使得下标直接对应数值1-100，方便直接访问和操作。
• 循环边界优化：int(math.Sqrt(100)) 计算结果为10。对于寻找N以内的素数，只需筛选到 sqrt(N) 即可，因为大于此值的因子必然已在之前的小因子筛选中被处理过。
• 格式控制：引入计数器 n，每打印10个素数便执行一次 fmt.Println()，使输出结果更易读。

以上就是Go语言利用筛选法求100以内素数的详细内容，更多关于Go算法基础与素数判断的资料请关注本站其它相关文章！