Project Euler——Problem 3

daybreakcx posted @ 2009年7月14日 01:23 in Prject Euler , 978 阅读

原题与答案：

Problem 3

02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Answer:6857

分析与解答：

题目的大意是求600851475143的最大质因子，这个问题的解决也很容易，只要将每个因子都试除从中取出最大的即可，但是要注意的是，如果单独去一个个试除的话，必然会导致运算的时间非常的久，我们考虑只需要计算到 $\sqrt{600851475143}=775146$ 即可，因为如果有素因子大于这个数，那么通过对于小等于775146的素数的试除，剩下的数值一定是一个素数。所以我们可以一边利用筛法进行素数生成，一边进行试除将原来的数值变小，在C中这个题目的数值记录要用到64位整数，具体实现代码如下：

#include<stdio.h>
#include<string.h>
long long s,i,j,ans;
bool nprime[775147];
int main()
{
s=600851475143LL;
memset(nprime,false,sizeof(nprime));
for (i=2;i<=775146;i++)
if (!nprime[i])
{
if (s%i==0) ans=i;
while (s%i==0) s/=i;
if (s==1) break;
for (j=i*i;j<=775146;j+=i) nprime[j]=true;
}
if (s!=1) ans=s;
printf("%lld\n",ans);
return 0;
}