UVA 10699 Count the factors 题解

cautx 2019-08-30 原文

UVA 10699 Count the factors 题解

Time limit: 3000 ms
OS: Linux

Write a program, that computes the number of different prime factors in a positive integer.
Input
The input tests will consist of a series of positive integers. Each number is on a line on its own. The
maximum value is 1000000. The end of the input is reached when the number `0′ is met. The number
`0′ shall not be considered as part of the test set.
Output
The program shall output each result on a line by its own, following the format given in the sample
output.
Sample Input
289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0
Sample Output
289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3

题意：给出一个数n，问n有多少个质因数。

分析：因为n<=1000000，time limit 3000ms，所以直接枚举所有当前小于n的素数即可。

欧拉筛预处理素数。

在枚举素数的过程中，如果该素数是n的质因数，那么就把n不断地除去该素数直到小于该素数，如果当前枚举的素数大于n，直接break即可。

AC code:

#include<bits/stdc++.h>
using namespace std;
bool u[1000005];
int su[1000005];
int num;
void olas()
{
    num=1;
    memset(u,true,sizeof(u));
    for(int i=2;i<=1000000;i++)
    {
        if(u[i])    su[num++]=i;
        for(int j=1;j<num;j++)
        {
            if(i*su[j]>1000000)    break;
            u[i*su[j]]=false;
            if(i%su[j]==0)    break;
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    olas();
    int n;
    while(~scanf("%d",&n)&&n)
    {
        int tmp=n;
        int ans=0;
        for(int i=1;i<num;i++)
        {
            if(n<su[i])    break;
            if(n%su[i]==0)
            {
                ans++;
                while(n%su[i]==0)
                {
                    n/=su[i];
                }
            }
        }
        printf("%d : %d\n",tmp,ans);
    }
    return 0;
}