判断质数

判断 n 能否能被 √n 以内的某个大于 1 的整数整除，如果不能则说明 n 是质数

func isPrime(n int) bool {
    for i := 2; i*i <= n; i++ {
       if n%i == 0 {
          return false
       }
    }
    return n >= 2
}

筛质数

// 埃氏筛
// 判断小于 n 的所有自然数是否为质数
func isNotPrime(n int) []bool {
    notPrime := make([]bool, n)
    // 0 和 1 不是质数
    notPrime[0], notPrime[1] = true, true
    for i := 2; i*i < n; i++ {
       if !notPrime[i] {
          // 从 i*i 开始，因为 2/3/.../(i-1) * i 已经被处理过了
          for j := i * i; j < n; j += i {
             notPrime[j] = true
          }
       }
    }
    return notPrime
}

LeetCode 相关题目：3896. 将数组转换为交替质数数组的最少操作次数