1295. 质因数统计

1295. 质因数统计

中文English

题目给定一个正整数N，你需要统计(1,N]之间所有整数质数分解后，所有质数的总个数。

样例

输入：6
输出：7
解释：2=2, 3=3, 4=2*2, 5=5, 6=2*3, 个数和为1+1+2+1+2=7

注意事项

1<N<=100000

class Solution:
    """
    @param N: a number
    @return: the number of prime numbers.
    """
    """
    1.动态规划
    转移方程
    if (i%j == 0):
        dp[i] = dp[i//j] + dp[j]
    """
    def Count_PrimeNum(self, N):
        dp = [0 for _ in range(N + 1)]
        
        #计算顺序
        for i in range(2,N + 1):
            for j in range(2,i + 1):
                dp[i] = 1
                if (i%j == 0):
                    dp[i] = dp[i//j] + dp[j]
                    break 
        
        return sum(dp)

注：lintcode未通过，时间复杂度问题，待优化。