Project Euler——Problem 3 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 2
Project Euler——Problem 4

Project Euler——Problem 3

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

原题与答案:

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位整数,具体实现代码如下:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. long long s,i,j,ans;
  4. bool nprime[775147];
  5. int main()
  6. {
  7.         s=600851475143LL;
  8.         memset(nprime,false,sizeof(nprime));
  9.         for (i=2;i<=775146;i++)
  10.                 if (!nprime[i])
  11.                 {
  12.                         if (s%i==0) ans=i;
  13.                         while (s%i==0) s/=i;
  14.                         if (s==1) break;
  15.                         for (j=i*i;j<=775146;j+=i) nprime[j]=true;
  16.                 }
  17.         if (s!=1) ans=s;
  18.         printf("%lld\n",ans);
  19.         return 0;
  20. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter