应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三题：寻找600851475143的最大质因子
北京石油化工学院2026年研究生招生接收调剂公告
71/1返回列表
查看: 3896  |  回复: 18
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 7 个 程序强帖 ，点击这里进行查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

微尘、梦想

专家顾问

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
xzhdty(金币+1): 谢谢微尘、梦想 斑斑 2011-05-10 15:10:46
余泽成(程序强帖+1): 2011-05-12 19:07:28
CODE:
#include "stdio.h"
void main(void)
{
    int i,a;
    printf("请输入一个整数：" );
    scanf("%d",&a);

    for(i=2;a!=1;i++)
        if(a%i==0)
        {
            a/=i;
            printf("%d\t",i);
            i--;
        }
        printf("\n" );
}

由于32位内存的限制，无法求出太大的数！

[ Last edited by 微尘、梦想 on 2011-5-12 at 16:19 ]
赞一下(3人) 回复此楼
任风云变幻，我笑对人生！
2楼2011-05-10 13:19:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

智能机器人

Robot (super robot)

我们都爱小木虫

找到一些相关的精华帖子，希望有用哦~

科研从小木虫开始，人人为我，我为人人

libralibra

兑换贵宾

骠骑将军

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
xzhdty(金币+2): 呵呵谢谢应助 2011-05-10 15:11:23
余泽成(程序强帖+1): 2011-05-12 19:07:37
此题很变态,matlab运行55s,
CODE:
function result = euler3()
tic;
result = 0;
n = 600851475143;
for i=3:sqrt(n)
    if isprime(i)==1 && mod(n,i)==0
        result = i;
    end
end
toc;
end

答案
CODE:
Elapsed time is 55.277722 seconds.
ans =
        6857

[ Last edited by libralibra on 2011-5-10 at 16:46 ]
赞一下(3人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
3楼2011-05-10 13:58:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

超级版主

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★
余泽成(金币+2, 程序强帖+1): 辛苦了！ 2011-05-12 19:08:14
写了一个python版的，不知道算不算筛选的。
CODE:
import timeit
from math import sqrt

def euler3():
    n = 600851475143

    primes = range(2, int(sqrt(n)))

    while n > 1:
        prime = primes[0]
        if n % prime == 0:
            print prime
            n = n / prime
        primes = [x for x in primes if x % prime != 0]


t = timeit.Timer("euler3.euler3()", "import euler3")
print t.timeit(1)

在我的电脑上用时不到20秒
不过，应该还能优化。因为用Mathematica不到1秒

PS:这个sqrt(n)假设好像有问题啊。比如本题的数分解为71, 839, 1471, 6857，如果是后两个数的积是10086647，开根号是3175.9，显然找不到后面一个数了啊。

[ Last edited by holmescn on 2011-5-12 at 11:15 ]
赞一下(1人) 回复此楼
9楼2011-05-12 10:14:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

主管区长

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★ ★
余泽成(金币+3, 程序强帖+1): 鼓励交流！ 2011-05-12 19:10:07
为了说明微尘版主的观点不对，以及我也不知道我自己的想法对不对，我写了一个C++版的计算。之所以用了N久不用的C++，是因为我不想自己实现一个list，哈哈。不过，好像并没有比matlab快多少。

虽然600851475143不能用一个32位的int表示，但显然它的位数少于15，就可以用一个double来保存啊。当然，查卷的算法就要换用适合double的了。
CODE:
#include
#include
#include

using namespace std;

int main(int argc, char** argv){

    double n = 600851475143.0;
    list primes;

    for(int i = 2; i < sqrt(n); i++)
        primes.push_back(i);

    while(n > 1.0){
        double prime = primes.front();
        if(fmod(n, prime) == 0){
            cout<             n /= prime;
        }

        list::iterator it;
        primes.erase(primes.begin());

        for(it = primes.begin(); it != primes.end(); it++){
            if(fmod(*it, prime) == 0)
                it = primes.erase(it);
        }
    }
}

[ Last edited by holmescn on 2011-5-12 at 15:10 ]
赞一下(1人) 回复此楼
11楼2011-05-12 11:13:34
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

专家顾问

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★ ★
余泽成(金币+3, 程序强帖+1): 越来越快，呵呵！ 2011-05-12 19:10:53
这回可能叫双筛选了吧，果然很牛啊，本来以为不会太快呢，看来是我的脑子太慢了。
先给出matlab的程序。其它语言需要有动态链表的支持。
CODE:
clear;
primes = [2];
n = 600851475143;
tic;
while n > 1
    m = length(primes);
    prime = primes(m)+1:primes(m)+m;
    for i = 1:m
        prime(find(mod(prime, primes(i))==0)) = [];
    end
    for i = 1:length(prime)
        if mod(n, prime(i)) ==0
            fprintf('%d\n', prime(i));
            n = n / prime(i);
        end
    end
    primes = [primes prime];
end
toc

如果是偶数，2需要预先处理一下。这个程序在我这里需要0.08s很爽了。

筛选法的原理是：用已知的质数当筛子过滤未知的数，去掉质数的倍数。余下的就是质数了。
赞一下(1人) 回复此楼
13楼2011-05-12 17:17:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

专家顾问

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与交流！ 2011-05-17 08:25:17
额 来晚了
大家的算法都不错
我也写个一个吧 c 语言的 迭代法
CODE:
#include
#include
#include

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();
#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);

int euler2(int a, long long n){
  int i=0;
  for(i=a;i     if(n%i==0){
      printf("%d*",i);
      return euler2(i,n/i);
    }
  }
  printf("%lld\n",n);
  return n;
}



int main(void){
long long n=600851475143;
int repeat_num = 10000;

TIMERSTART;

while( repeat_num-- ){
   euler2(2,n);
}

TIMERSTOP;

  return 0;
}

重复10000次，可能时间获得的不是很准阿
我32位linux (64位不确定有没有问题)
运行结果
CODE:
...
71*839*1471*6857
71*839*1471*6857
elapsed time=0.550000 seconds.
赞一下(2人) 回复此楼
15楼2011-05-16 21:53:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zdapeng

实习版主

优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！优秀！！有木有！！！
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与交流！ 2011-06-02 00:08:12
#include
#include
using namespace std;
/*问题分析：
寻找最大质因数，只需要按从小到大的质数遍历
如果质素是该数的因数，则与之相除，直至不再是其因数
当该数变为1时，此时的质因数即为其最大质因数
*/
double getin()
{cout<<"please input a number:";
double aim;
cin>>aim;
return(aim);
}
int CheckPrime(int i)
{int j;
for(j=2;j<=sqrt(i);j++)
    if(i%j==0)
       return(0);
return(1);
}
double divide(double aim,int i)
{for(;fmod(aim,i)==0
    aim=aim/i;
return(aim);
}
int main()
{int i;
double aim;
aim=getin();
for(i=2;i<=aim;i++)
     if(CheckPrime(i))
        aim=divide(aim,i);
cout<<"the answer is "<<(i-1)< char sign;
cin>>sign;
exit(0);
}
几乎是enter就给出结果。
赞一下(2人) 回复此楼
16楼2011-06-01 14:27:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
71/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 271求调剂 +10 勒布朗@ 2026-03-31 12/600 2026-04-01 07:25 by sunshine0013
[考研] 材料专业调剂 +3 啦啦啦哭 2026-03-31 3/150 2026-04-01 01:27 by 小懒虫不懒了
[考研] 289求调剂 +7 BrightLL 2026-03-29 7/350 2026-03-31 22:05 by 544594351
[考研] 339求调剂 +3 zjjkt 2026-03-31 3/150 2026-03-31 20:34 by 83503孙老师
[考研] 318求调剂 +3 笃行致远. 2026-03-31 3/150 2026-03-31 20:27 by 求调剂zz
[考研] 086000调剂 +5 7901117076 2026-03-26 5/250 2026-03-31 17:45 by 544594351
[考研] 353求调剂 +3 江上枫_26 2026-03-28 3/150 2026-03-31 15:53 by jp9609
[考研] 求收留 +8 1943443204 2026-03-28 8/400 2026-03-31 15:00 by -迷了路啊路
[考研] 一志愿郑大材料工程290求调剂 +12 Youth_ 2026-03-30 12/600 2026-03-31 03:34 by 蒙奇奇521
[考研] 303求调剂 +7 DLkz1314. 2026-03-30 7/350 2026-03-30 21:07 by peike
[考研] 310求调剂 +10 争取九点睡 2026-03-30 10/500 2026-03-30 16:45 by ztnimte
[考研] 0703化学/290求调剂/本科经历丰富/工科也可 +13 丹青奶盖 2026-03-26 15/750 2026-03-30 12:35 by fangnagu
[考研] 283求调剂（080500） +14 A child 2026-03-27 14/700 2026-03-30 12:06 by 探123
[考研] 求调剂 +4 QiMing7 2026-03-25 5/250 2026-03-29 21:10 by 唐沐儿
[考研] 2026年华南师范大学欢迎化学，化工，生物，生医工等专业优秀学子加入！ +3 llss0711 2026-03-28 6/300 2026-03-29 10:26 by llss0711
[考研] 材料与化工（0856）304求B区调剂 +8 邱gl 2026-03-27 8/400 2026-03-28 12:42 by 唐沐儿
[考研] 330一志愿中国海洋大学 化学工程 085602 有读博意愿 求调剂 +3 wywy.. 2026-03-27 4/200 2026-03-28 03:32 by fmesaito
[考研] 调剂 +4 柚柚yoyo 2026-03-26 4/200 2026-03-26 20:43 by fmesaito
[考研] 296求调剂 +4 汪！？！ 2026-03-25 7/350 2026-03-25 16:41 by 汪！？！
[考研] 求调剂 +3 李李不服输 2026-03-25 3/150 2026-03-25 13:03 by cmz0325
信息提示
关闭
请填处理意见
关闭