九度OJ1207

题目给你了一个很大的n,然后让你去计算它的质因数。对N进行开方得到的是一个大约在32000左右的数,我们可以用埃氏筛法进行素数打表。对所有prime[i]<=sqrt(n),分别看prime[i]能否整除n,若能整除就用n/=prime[i]然后继续寻找即可。值得注意的是,当我们搜寻完素数表中的所有元素后,如果n>1,说明除完诸多质因数后n已经成为了一个大于sqrt(n)的质数(这样的数在n的质因数乘法公式中不可能有两个),此时再将之前的计数加1即可。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 31623
int n,top=0;
int prime[N];
char ifprime[N]={0};
int main()
{
int i,j;
memset(ifprime,1,sizeof(ifprime));
for(i=2;i<=N-1;i++)
if(ifprime[i]==1)
{
prime[top++]=i;
for(j=i*i;j<=N-1;j+=i)
ifprime[i]=0;
}
while(scanf("%d",&n)!=EOF)
{
int count=0;
double d=sqrt(n);
int dn=d;
for(i=0;prime[i]<=dn;i++)
{
while(n%prime[i]==0)
{
n=n/prime[i];
count++;
if(n==1)
break;
}
}
if(n!=1)
count++;
printf("%d\n",count);
}
return 0;
}

  

上一篇:C# 词法分析器(二)输入缓冲和代码定位


下一篇:codeforces Gargari and Permutations(DAG+BFS)