华为 OD 面试简便算法 - 求质数的个数

题目描述

给定整数n，返回所有小于n的素数的数量

思路分析

题目比较简单，重点在于如何判断一个数是否为素数-“只能被自身和1整除”。对于给定的n：

若n < 2：直接返回0；否则遍历2-n判断当前数是否为素数，为素数时count+1，最后返回count。

代码实现

func GetPrimeNumber(n int) int {
	count := 0
	if n < 2 {
		return count
	}
	for i := 2; i < n; i++ {
		if isPrime(i) {
			count++
		}
	}
	return count
}

func isPrime(num int) bool {
	for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
		if num%i == 0 {
			return false
		}
	}
	return true
}