Largest prime factor
Time Limit: 5000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3961Accepted Submission(s): 1393
Problem Description
Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.
Input
Each line will contain one integer n(0 < n < 1000000).
Output
Output the LPF(n).
Sample Input
Sample Output
Author
Wiskey
Source
用筛选法AC
//求一个数的最大素因子是第几个素数,打表
#include <stdio.h>
#include <string.h>
#define N 1000000
int a[N];
int main()
{
int n=0,i,t,j;
memset(a,0,sizeof(a));
for(i=2;i<=N;i++)//对当前数的每个数的倍数进行赋值素数编号 可以覆盖哦 因为要覆盖为最大因子
{
if(a[i]==0)
{
n++;//素数i的位置
for(j=i;j<=N;j+=i)//构造出j的暂时最大素数因子的位置
a[j]=n;
}
}
while(scanf("%d",&i)!=EOF)
{
printf("%d\n",a[i]);
}
return 0;
}
如果用打印素数表后 然后分解质因子 找到最大质因子 输出对应位置超时 贴下超时代码
#include<stdio.h>
#include<math.h>
#include<string.h>
int vis[1000000+100];
int prime[80000],c;
void get_prime()
{
int i,j,n,m;
c=0;
n=1000000;
m=(int)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(i=2;i<=m;i++) if(!vis[i])
{
for(j=i*i;j<=n;j+=i) vis[j]=1;
}
for(j=2;j<=n;j++) if(!vis[j])
prime[c++]=j;
}
int main()
{
int j,n,max;
get_prime();
while(scanf("%d",&n)!=EOF)
{
if(n==1) {printf("0\n");continue;}
max=0;
for(j=0;j<c;j++)
{
if(n<prime[j]) break;
while(n%prime[j]==0)
{
n/=prime[j];
if(j>max) max=j;
}
}
printf("%d\n",max+1);
}
return 0;
}
分享到:
相关推荐
Largest prime factor Everybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor. The position of prime 2 is 1, prime 3 is 2,...
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
这个是杭电hdu的一个分类,新手们可以按照这个来刷题!
HDU最全ac代码
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
hdu2000-2014ac代码,虽然只有几道,但都是简单的