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

墨蓝 2022-06-07 00:23 151阅读 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 条评论，151人围观）

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

相关阅读

相关 Java题目解析——分解因数

题目描述： > 所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1 ≤ a2 ≤ a3

短命女/ 2023年09月30日 23:02/ 0 赞/ 27 阅读

相关刷题_31：分解因数

一.分解因数题目链接： > [分解因数][Link 1] 题目描述： > 所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2

以你之姓@/ 2023年09月30日 22:42/ 0 赞/ 33 阅读

相关 C语言实现因数分解

笔者使用CFree编译器，实现了对输入的任意因数进行分解的功能，相当于Matlab中的factor函数。 \include <stdio.h> \include <ma

墨蓝/ 2023年07月19日 12:06/ 0 赞/ 21 阅读

相关整数分解(integer factorization)

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

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

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

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

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

相关分解因数

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

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

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

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

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

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

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

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

相关 Codeforces 151C(分解因数)

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

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

相关分解机(Factorization Machines)

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

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