算法：求小于指定数字n的每个数字的质数数量之和

写在前面

今天面试遇到一个算法题，不难，但是没有想到最优解，记录一下

题目描述

给定一个数字n(2<=n<=100)，计算[2,n]之间每个数字的质数的数量，返回总和

示例：n=8

解析：2=2,3=3,4=22,5=5,6=23,7=7,8=222

返回结果1+1+2+1+2+1+3=11

简单代码

func SumPrime(n int) int {
	sum := 0
	for i := 2; i <= n; i++ {
		sum += countPrime(i)
	}
	return sum
}

// 求每个数字n的质数数量
func countPrime(n int) int {
	result := 0
	for i := 2; i <= n; i++ {
		for n%i == 0 {
			result++
			n /= 2
		}
		if n == 1 {
			break
		}
	}
	return result
}

拿到题目第一反应的思路是上面这个，并且很快写出来了。这个算法的时间复杂的太高了，而且做了很多重复的计算，面试官问有没有好的解决方案。

思考之后，觉得可以做个缓存，比如计算8的时候，发现8能被4整除，那countPrime(8)=countPrime(4)+1

这不就是动态规划思路吗？于是用动态规划思路重新写了一遍

动态规划解法

func SumPrimeDynamic(n int) int {
	dp := make(map[int]int)
	dp[2] = 1
	sum := 1
	for i := 3; i <= n; i++ {
		find := false
		for j := 2; j <= n; j++ {
			if i%j == 0 {
				v := dp[i/j]
				dp[i] = v + 1
				find = true
				break
			}
		}
		if !find {
			dp[i] = 1
		}
		sum += dp[i]
	}
	return sum
}

对比

func BenchmarkSumPrime(t *testing.B) {
	for i := 0; i < t.N; i++ {
		SumPrime(10000)
	}
}

func BenchmarkSumPrimeDynamic(t *testing.B) {
	for i := 0; i < t.N; i++ {
		SumPrimeDynamic(10000)
	}
}

结果

BenchmarkSumPrime-12                 110          10694065 ns/op
BenchmarkSumPrimeDynamic-12          297           4020002 ns/op

当n很大的时候，这两个算法差不不大。但是当n很小的时候，SumPrime比SumPrimeDynamic要快一些

func BenchmarkSumPrime(t *testing.B) {
	for i := 0; i < t.N; i++ {
		data20240410.SumPrime(10)
	}
}

func BenchmarkSumPrimeDynamic(t *testing.B) {
	for i := 0; i < t.N; i++ {
		data20240410.SumPrimeDynamic(10)
	}
}

结果

BenchmarkSumPrime-12            25432356                46.82 ns/op
BenchmarkSumPrimeDynamic-12      4213293               284.2 ns/op

不知道是什么原因