NYOJ--520

最大素因子

原题链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=520

分析：先筛素数，同时记录下素数的序号，然后质因数分解。

 1  
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #define maxn 1000005
 6 using namespace std;
 7 int cnt,num;
 8 long long n;
 9 bool flag[maxn]={0};
10 int prime[maxn];
11 int count[maxn]={0};
12 int por[maxn];
13 int cpor[maxn];
14 void isprime()
15 {
16     cnt=0;
17     for(int i=2;i<=maxn;i++)
18     if(!flag[i])
19     {
20         prime[cnt++]=i;count[i]=cnt;
21         for(int j=2;i*j<=maxn;j++)
22         flag[i*j]=true;
23     }
24 }
25 void fen(int n)
26 {
27     num=0;
28     for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
29     {
30         if(n%prime[i]==0)
31         {
32             por[num]=prime[i];
33             cpor[num]=0;
34             while(n%prime[i]==0)
35             {
36                 cpor[num]++;
37                 n/=prime[i];
38             }
39             num++;
40         }
41     }
42     if(n>1)
43     {
44         por[num]=n;
45         cpor[num++]=1;
46     }
47 }
48 
49 int main()
50 {
51     isprime();
52     int n;
53     while(scanf("%d",&n)!=EOF)
54     {
55         if(n==1){printf("0
");continue;}
56         fen(n);
57         printf("%d
",count[por[num-1]]);
58     }
59     return 0;
60 }
61

View Code