求素数因子的位置

求素数因子的位置

时间： 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;
}

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