UVA - 10699 - Count the factors（分解素因数）-蒲公英云

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

墨蓝 2022-06-07 00:23 256阅读 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;
}