关于leetcode:Golang力扣Leetcode初级算法数学计数质数厄拉多塞筛法

5次阅读

共计 833 个字符,预计需要花费 3 分钟才能阅读完成。

题目 :统计所有小于非负整数 n 的质数的数量。

链接 :力扣 Leetcode—高级算法—数学—计数质数.

示例 1

输出:n = 10
输入:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。

示例 2

输出:n = 0
输入:0

示例 3

输出:n = 1
输入:0

标签 :数组、数学、枚举、数论

思路 :如果用暴力破解,那么毫无疑问会超时,咱们能够用厄拉多塞筛法(Eratosthenes):即从 2 开始,2 的倍数全副去掉;接下来 3 是质数,3 的倍数全副去掉,如此上来,留下的都是质数。

  • 咱们首先定义一个长度为 n 的 bool 数组,用来标识某个数是否是素数,如果不是素数就将数组中对应的地位置为 true
  • 首先,0 和 1 必定不是质数,所以数组前两个元素的值置为 true
  • 数组中初始化的时候每个元素对应的值都是 false,从 2 开始,如果对应数组中的值还是 false,那么阐明了这个数肯定是质数
  • 所以 2 是质数,那么将 2 翻倍的数肯定不是质数,所以咱们将 2 始终这样翻倍翻下去,直到某一个倍数超过 n,那么数组中就没有对应的地位了,咱们在这个过程中,将翻倍失去的数字在数组中对应的地位置为 true
  • 而后遍历 2 的下一个数,首先看这个数在数组中对应地位的值是 true 还是 false,如果是 true 阐明了这个地位是由后面某个数翻倍失去的,阐明他是合数,所以跳过,如果是 false,阐明了这个数不能由后面的数翻倍失去,那么他必定是质数
  • 始终反复上述过程,直到这个 2 变成了最初的 n

次要 Go 代码如下:

package main

import "fmt"

func countPrimes(n int) int {list := make([]bool, n)
    sum := 0

    for i := 2; i < n; i++ {if list[i] == false {sum++}
        for j := i + i; j < n; j += i {list[j] = true
        }
    }
    return sum
}

func main() {
    var n int
    fmt.Scanf("%d", &n)
    fmt.Println(countPrimes(n))
}

提交截图

正文完
 0