本文共 884 字，大约阅读时间需要 2 分钟。

领扣LintCode算法问题答案-1295. 质因数统计

1295. 质因数统计

描述

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

• 1<N<=100000

样例 1：

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

题解

public class Solution {
       /**     * @param N: a number     * @return: the number of prime numbers.     */    public int Count_PrimeNum(int N) {
           //         int ret  = 0;        boolean[] vis   = new boolean[100001];        int[]     prime = new int[100001];        Arrays.fill(prime, 1);        for (int i = 2; i <= N; i++) {
               ret += prime[i];            for (int j = 2; j <= i && i * j <= N; j++) {
                   if (vis[i * j]) {
                       continue;                }                vis[i * j] = true;                prime[i * j] = prime[i] + prime[j];            }        }        return ret;    }}

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。

欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

转载地址：https://le-yi.blog.csdn.net/article/details/108907479 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！