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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三题：寻找600851475143的最大质因子
192/2返回列表上一页12
查看: 3810  |  回复: 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
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低 +10 瞬息宇宙 2026-02-20 13/650 2026-02-23 11:23 by holypower
[考研] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 khieu8v8m0 2026-02-22 8/400 2026-02-23 09:35 by w4l55oybr1
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 8/400 2026-02-23 09:29 by w4l55oybr1
[考研] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +5 usprnugpzw 2026-02-21 11/550 2026-02-23 09:24 by w4l55oybr1
[教师之家] 为什么中国大学工科教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？ +5 欢乐颂叶蓁 2026-02-21 8/400 2026-02-23 09:19 by 欢乐颂叶蓁
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 w89i99eaeh 2026-02-22 5/250 2026-02-23 08:04 by w4l55oybr1
[博后之家] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 6/300 2026-02-23 07:59 by w4l55oybr1
[博后之家] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +6 3dfhjxgsh7 2026-02-22 9/450 2026-02-23 07:49 by w4l55oybr1
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 4/200 2026-02-23 06:46 by jsjzfl
[公派出国] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 khieu8v8m0 2026-02-22 5/250 2026-02-23 06:29 by w4l55oybr1
[硕博家园] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 8/400 2026-02-23 06:24 by w4l55oybr1
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +5 3dfhjxgsh7 2026-02-22 6/300 2026-02-23 02:04 by 5jlh3qtdvx
[教师之家] 版面费该交吗 +7 苹果在哪里 2026-02-22 8/400 2026-02-22 22:37 by otani
[基金申请] 面上可以超过30页吧？ +4 阿拉贡aragon 2026-02-22 4/200 2026-02-22 21:22 by 山西悬空寺空悬�
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 usprnugpzw 2026-02-21 6/300 2026-02-22 19:48 by w89i99eaeh
[考研] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 3dfhjxgsh7 2026-02-22 4/200 2026-02-22 16:52 by khieu8v8m0
[找工作] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 usprnugpzw 2026-02-22 3/150 2026-02-22 16:37 by khieu8v8m0
[公派出国] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 usprnugpzw 2026-02-21 4/200 2026-02-22 16:27 by khieu8v8m0
[基金申请] 什么是人一生最重要的？ +4 瞬息宇宙 2026-02-21 4/200 2026-02-22 11:44 by huagongfeihu
[基金申请] 今年春晚有几个节目很不错，点赞！ +11 瞬息宇宙 2026-02-16 12/600 2026-02-21 21:14 by lq493392203
信息提示
关闭
请填处理意见
关闭