求素数因子的位置

时间: 1ms        内存:128M

描述:

每个人都知道任何数字都可以由素数组合。
现在,你的任务是告诉我给定一个常数求最大的素数因子的位置(largest prime factor.)。
例如素数2的位置为1,素数3位置为2,素数5的位置为3 ……
那么4的最大素因子为2,那么LPF(4)=1,同理LPF(8)=1,而LPF(6)=2,因为最大素因子是3 ;
LPF(9)=2,因为9=3*3,最大素因子为3……
特别地,LPF(1)= 0。

输入:

每行将包含一个整数n(0 <n <1000000)。

输出:

输出 LPF(n).

示例输入:

1
2
3
4
5

示例输出:

0
1
2
1
3

提示:

参考答案(内存最优[1132]):

#include<stdio.h>
#include<math.h>
int main()
{
	int isprime(int);
	int n;
	while(~scanf("%d",&n))//输入一个是数
	{
		int i,j,k;//定义三个变量
		int sum=0;//最大素数因子的位置
		if(n==1)
		{
			printf("%d\n",0);//如果输入的数为1
		}
		else 
		{
			for(i=2;i<=n;i++)//求出这个数的最大质因数,赋值给k;
			{
				if((isprime(i)==1)&&(n%i==0))
					k=i;
			}
			for(i=2;i<=k;i++)
			{
				if(isprime(i)==1)
					sum++;
			}
			printf("%d\n",sum);
		}
	}
	return 0;
}
int isprime(int n)//判断素数
{
	int i;
	for(i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		return 0;
	}
	if(i>sqrt(n))
		return 1;
}

参考答案(时间最优[2]):

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int t;
    cin>>t;
        while(t--)
        {
            int m;
            cin>>m;
            int c=m;
            m=m%10;
            int ans=1;
            while(c)
            {
                if(c&1==1)
                    ans=(ans*m)%10;
                m=(m*m)%10;
                c>>=1;
            }
            cout<<ans<<endl;
        }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。