九度OJ1207
2024-09-23 18:39:36
题目给你了一个很大的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;
}
最新文章
- RunLoop 总结:RunLoop的应用场景(二)
- Hibernate inverse用法(转载)
- java学习笔记--this 关键字的理解
- ExtJS -- Grid 文本居中显示
- 获得输入框的文本document.getElementById(&#39;id&#39;).value;
- HDU 5834 [树形dp]
- 将大数据利用 BCP 导出SqlServer数据到CSV
- 闭包(Closures)
- zoj 1010 Area【线段相交问题】
- ll的命令后面的字段详解
- CentOS6.5内 MySQL5.7.19编译安装
- CS Academy Gcd on a Circle(dp + 线段树)
- Arduino IDE for ESP8266教程(三)HTTP客户端
- Java XML JSON 数据解析
- 拦截器的使用,配置手机浏览器访问的h5页面
- Enum学习中的compareTo方法分析
- SCLAlertView-Swift
- hdu 5839(三维几何)
- [Tomcat 部署问题] Undeployment Failure could not be redeployed ...
- python selenium --层级定位
热门文章
- 学习Python遇到的那些坑
- JAVA利用ODBC读取DBF,可以解决javadbf.jar对DBF部分中文乱码和错行等杂症
- RMAN备份数据库与恢复数据库(整库)
- LINQ学习入门教程(一)
- TextArea限制输入长度
- js Number越界比较.
- Neutron分析(3)—— neutron-l3-agent
- HackerRank ";The Indian Job";
- LintCode ";Copy Books";
- (C#) 创建单元测试(Unit Test).