UVA - 10699 - Count the factors（分解素因数）

墨蓝 2022-06-07 00:23 131阅读 0赞

给出一个很大的数，然后判断素因数的个数，我们先打一个素数数组，里面全存的是素数；  
然后注意判断是否可以被整除，如果可以就一口气除到不能除尽为止，然后换下一个素数，继续上述操作；

#include<iostream>
    #include<cstring>
    #include<cmath>
    #define MAXN 1000005
    #define ll long long 
    
    using namespace std;
    
    bool isprime[MAXN];
    int prime[MAXN];
    int num = 1;
    
    int getprime(int n) {
       //存入isprime数组中
        memset(isprime, true, sizeof(isprime));
        prime[num++] = 2;
        isprime[0] = isprime[1] = false;
        for(int i = 3; i <= n; i+=2) {
            if(isprime[i]) {
                prime[num++] = i;
                for(int j=i+i; j <= n; j+=i) {
                    isprime[j] = false;
                }
            }
        }
    }
    
    int main() {
        ll n;
        getprime(MAXN);
        while(cin >> n && n) {
            int x = n;
            int i = 1, ans = 0, flag;
            for(;;) {
                flag = 0;
                while(x % prime[i] == 0) {
       //除尽为止
                    x /= prime[i];
                    flag = 1;//标记曾经除过，
                } 
                if(flag) ans++;
                i++;//除完需要换下一个素数
                if(x == 1 || i >= num) break;//结束的条件就是本身变成了1，或者超过了最大的素数。
            }
            printf("%d : %d\n", n, ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关线性代数：矩阵分解(Matrix factorization)

矩阵分解算法由奇异值分解算法（Singular Value Decomposition, SVD）演变而来，传统的奇异值分解算法只能对数据稠密的矩阵进行分解，而评分矩阵是极度稀

末蓝、/ 2023年10月05日 16:34/ 0 赞/ 4 阅读

相关整数分解(integer factorization)

整数分解在数学中，整数分解（英语：integer factorization）又称素因数分解（prime factorization），是将一个正整数写成几个约数的乘积

我会带着你远行/ 2023年01月20日 06:53/ 0 赞/ 6 阅读

相关 Hdu 1395 2^x mod n = 1 (欧拉定理分解素因数)

先吐槽一下：考完试后第一天实验室就断网，简直不可思议。题意：给出n,找出最小的x使其满足2^x mod n = 1 思路：欧拉定理（费马小定理的欧拉推广）可得如果n为1或

阳光穿透心脏的1/2处/ 2022年09月19日 12:11/ 0 赞/ 139 阅读

相关分解素因子

分解素因子 Time Limit: 1500ms Memory limit: 10000K 有疑问？点这里^\_^ 题目描述假设x是一个正整数，它的值不超过

￡神魔★判官ぃ/ 2022年08月10日 05:52/ 0 赞/ 192 阅读

相关 UVa-129-Krypton Factor

Problem 问题 You have been employed by the organisers of a Super Krypton Factor Conte

男娘i/ 2022年07月10日 11:29/ 0 赞/ 137 阅读

相关分解因数

描述给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 \ a2 \ a3 \ ... \ an，并且1 < a1 <= a2 <= a3 <= ... <=

柔光的暖阳◎/ 2022年06月13日 08:56/ 0 赞/ 167 阅读

相关 UVa10791 - Minimum Sum LCM （分解因数）

输入n，求两个正整数，是他们的最小公倍数为n，并且是其中最小的一组，输出他们的和。唯一分解定理 n=ap1 \ bp2 \ cp3…… 任何一个大于1的自然数 N,如果

Love The Way You Lie/ 2022年06月08日 10:09/ 0 赞/ 167 阅读

相关 UVA - 10699 - Count the factors（分解素因数）

给出一个很大的数，然后判断素因数的个数，我们先打一个素数数组，里面全存的是素数；然后注意判断是否可以被整除，如果可以就一口气除到不能除尽为止，然后换下一个素数，继续上述操

墨蓝/ 2022年06月07日 00:23/ 0 赞/ 132 阅读

相关 Codeforces 151C(分解因数)

问题描述: You can't possibly imagine how cold our friends are this winter in Nvodsk! Two of

红太狼/ 2022年06月04日 07:44/ 0 赞/ 136 阅读

相关分解机(Factorization Machines)

[分解机(Factorization Machines)推荐算法原理][Factorization Machines] 转载于:https://www.cnblogs.c

Bertha 。/ 2021年12月11日 07:09/ 0 赞/ 307 阅读