基础

线性筛法

package main
import (
    "fmt"
    "os"
    "bufio"
    )

const N = 1000010

var (
    out = bufio.NewWriter(os.Stdout)
    in = bufio.NewReader(os.Stdin)

    cnt int // 质数数组的下标
    primes [N]int // 质数数组
    st [N]bool // 不用看的数：非质数
    )

func getPrimes(n int) (cnt int) {
    for i := 2; i <= n; i++{ // 从2开筛
        // 是质数，进入primes数组
        if !st[i] {primes[cnt] = i; cnt++} 
        // 对于合数，用他们各自的最小质因数筛掉
        for j := 0; primes[j] <= n / i; j++ { 
            // st数组打上TRUE, 这合数不用看了
            st[primes[j] * i] = true 
            // 找到primes[j]是i的最小质因数，break
            if i % primes[j] == 0 {break}
        }
    }
    return 
}

func main() {
    defer out.Flush()
    n := 0
    // 一个数的质数数量 == primes数组的下标cnt
    fmt.Fscan(in, &n)
    // 打印质数数组
    fmt.Fprintln(out, getPrimes(n))

}

进阶: 预处理

在一些多次询问出结果的场合，可以先对整个数据范围筛出全局的质数数组，然后从头遍历出自己想要的质数