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

24小时热门版块排行榜    

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

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): 鼓励讨论！ 2011-05-12 19:10:35
算法说明：

以上用三种语言实现了同一个算法。下面简单说一下。

本题的主要想法是：找到每个质数，然后看看这个质数是不是给定的合数的因子。

要目的同学都使用了线性空间：即从2开始，看每个整数是不是一个质数，如果是质数，那是不是给定数的因子。

但有一点需要注意：如果2不是给定数的一个因子，那么2n也不是它的因子，所以就不用再试这些数了。我的算法就是基于这个思想，把m及m的倍数从可能解空间中除去，以减少找的次数。但这个算法现在有个问题，就是一开始的时候需要一个大数组来表示每一个数。如果我们可以算出下一下质数，那么其实就不需要在开始的时候记录这么多数了。能减少很多的空间开销。这个算法还在思考中....
赞一下(1人) 回复此楼
12楼2011-05-12 15:17:52
已阅   回复此楼   关注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的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 鼓励讨论！ 2011-05-13 21:25:06
引用回帖:
Originally posted by holmescn at 2011-05-12 10:31:11:
非常的悲催啊，同样的算法，在matlab里只用不到7秒
[code]
n = 600851475143;
tic;
primes = 2:round(sqrt(n));
while n > 1
    prime = primes(1);
    if mod(n, prime) == 0
        disp(num2str ...

对,我后面有些题也用primes直接生成素数,保存起来查找,效率提高太多了
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
14楼2011-05-12 19:16:06
已阅   回复此楼   关注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

金虫 (正式写手)
引用回帖:
Originally posted by zdapeng at 2011-06-01 14:27:58:
#include<iostream.h>
#include<math.h>
using namespace std;
/*问题分析：
寻找最大质因数，只需要按从小到大的质数遍历
如果质素是该数的因数，则与之相除，直至不再是其因数
当该数变为1时 ...

推荐使用BBCode发布代码，BBCode的用法，网上有很多.
赞一下 回复此楼
17楼2011-06-02 07:42:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

liandaoacc

新虫 (初入文坛)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
这是我写的，只验证了一些数，结果是对的，对于600851475143也是对的，但是没有经过仔细验证，所以不敢保证绝对对的。
#include <stdlib.h>
#include <map>
#include <iostream>
bool isPrime2(long n)
{
        if(n < 2)
                return false;
        if(n == 2)
                return true;
        if(n % 2 == 0)
                return false;
        for(long i = 3; i < n; i += 2)
        {
                if(n % i == 0)
                        return false;
        }
        return true;
}
void primeFactorDecomp(long long number, std::map<long, int> &primefactors)
{
        int size = primefactors.size();
        long beginprime = 2;
        long long numbercpy = number;
        int count = 0;
        if(size != 0)
        {
                std::map<long, int>::reverse_iterator rit = primefactors.rbegin();
                beginprime = rit->first;
                if(beginprime == 2)
                        beginprime += 1;
                else
                        beginprime += 2;
        }
        while(!isPrime2(beginprime))
        {
                beginprime += 2;
                if(beginprime > numbercpy)
                        return;
        }
        while(! (numbercpy % beginprime))
        {
                numbercpy /= beginprime;
                count++;
        }
        primefactors.insert(std::pair<long, int>(beginprime, count));
        primeFactorDecomp(numbercpy, primefactors);
}

int main(int argc, char** argv)
{
        long long number = 600851475143;
        std::map<long, int> primefactors;
        primeFactorDecomp(number, primefactors);
        std::map<long, int>::reverse_iterator rit = primefactors.rbegin();
        std::cout << rit ->first <<  '\n';
        return 0;
}
赞一下 回复此楼
18楼2013-11-17 22:12:16
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feign_te

金虫 (小有名气)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
如果已经有一个合适大小的素数列，肯定是最快的。
单独为一个问题去求素数列不太经济。
方法和前面一样，n除遍奇数找出第一个质因数p1之后，用n/p1找出下一个质因数p2，可代码写出来感觉差别好大啊。
CODE:
clear
tic
n = 600851475143;
prime=zeros(fix(log2(p)),1);
k=0;
m=n;
p=fix(n^.5);
r=3;
    for i =r:2:p
        if mod(m,i)==0
            k=k+1;
            r=i;         
            prime(k)=i;
            m=n/i;
            p=fix(m^.5);
            continue
        end     
    end
prime=prime(find(prime~=0))
toc

运行结果
CODE:
prime =
          71
         839
        1471
        6857
Elapsed time is 0.021253 seconds.
赞一下 回复此楼
19楼2013-12-10 06:53:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
192/2返回列表上一页12
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[有机交流] 3-溴吡啶-4-甲醛合成 10+3 雪糕也能爆炸 2026-03-31 9/450 2026-04-06 00:24 by nBu锂
[考研] 调剂 +3 李广火 2026-04-05 3/150 2026-04-05 18:57 by 蓝云思雨
[考研] 一志愿同济大学323分（080500）求调剂 +8 yikeniu 2026-04-01 8/400 2026-04-05 18:15 by cql1109
[考研] 348求调剂 +6 wukira 2026-04-04 6/300 2026-04-05 18:11 by 猪会飞
[考研] 数一英一274机械调剂 +5 星陨流霞 2026-04-04 6/300 2026-04-05 11:38 by arrow8852
[考研] 化学357分，考研调剂 +10 .Starry. 2026-04-04 11/550 2026-04-05 10:57 by cql1109
[考研] 298求调剂 +7 manman511 2026-04-05 7/350 2026-04-05 10:29 by 唐沐儿
[考研] 男生，一志愿沪9生物学071000，初试308求调剂 +3 刘墨墨 2026-04-04 3/150 2026-04-05 08:26 by barlinike
[考研] 348分环境工程·调剂 +10 吴彦祖24k 2026-04-03 11/550 2026-04-04 14:19 by 无际的草原
[考研] 一志愿北交大材料工程总分358 +6 cs0106 2026-04-03 6/300 2026-04-04 11:20 by w_xuqing
[考研] 一志愿北京科技大学材料工程085601，求调剂 +17 cdyw 2026-04-02 18/900 2026-04-04 11:14 by w_xuqing
[考研] 322求调剂 +6 FZAC123 2026-04-03 6/300 2026-04-03 22:23 by 科研小专家
[考研] 286求调剂 +8 lim0922 2026-04-02 8/400 2026-04-03 20:19 by rzh123456
[考研] 289-求调剂 +4 这里是_ 2026-04-03 4/200 2026-04-03 14:23 by 1753564080
[考研] 309求调剂 +14 呆菇不是戴夫 2026-04-02 14/700 2026-04-03 09:42 by 蓝云思雨
[考研] 一志愿山东大学化学与化工学院材料与化工专硕，360分求调剂 +4 不愿透露姓名的� 2026-04-02 4/200 2026-04-03 09:29 by 遗忘消失的灆
[考研] 交通运输考试264分求工科调剂 +4 jike777 2026-04-02 4/200 2026-04-02 21:53 by zllcz
[考研] 一志愿华南师范大学-22408计算机-292分-求华南师范大学调剂 +4 爱读书的小鳄鱼 2026-04-02 4/200 2026-04-02 18:35 by 求调剂zz
[考研] 08工科求调剂290分 +5 1314捧花 2026-04-02 8/400 2026-04-02 13:16 by 乔哒哒哒
[考研] 一志愿北京科技，085601总分305求调剂 +9 半生瓜！ 2026-04-01 11/550 2026-04-02 08:28 by Wang200018
信息提示
关闭
请填处理意见
关闭