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

24小时热门版块排行榜     石溪大学接受考研调剂申请>

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三题：寻找600851475143的最大质因子
【调剂】北京石油化工学院2024年16个专业接受调剂
192/2返回列表上一页12
查看: 2811  |  回复: 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
普通表情 龙 兔 虎 猫 高级回复(可上传附件) SCI英文润色翻译-EnPapers美团队-先修改后付款
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 298求调剂 +9 孙大大@ 2024-04-17 9/450 2024-04-19 21:50 by 刘国宁
[论文投稿] 最近遇到这样一个问题 2+4 asd123gfa689 2024-04-18 10/500 2024-04-19 18:57 by asd123gfa689
[找工作] 事业单位还是大学好？ +17 青萍之沫 2024-04-16 18/900 2024-04-19 17:45 by charles-c
[基金申请] 院士建议：对勇于提出解决卡脖子问题新解决方案的学者加大资助力度 +7 zju2000 2024-04-16 10/500 2024-04-19 11:10 by dwuab
[基金申请] 下雨了 +13 zju2000 2024-04-16 19/950 2024-04-19 09:24 by duxin_30
[论文投稿] 投稿求助 5+3 我是洲洲啊 2024-04-17 5/250 2024-04-18 17:13 by topedit
[考研] 0854计算机技术316分调剂，求求导师 捞我一下，有学就上 +6 zhushijie218 2024-04-16 7/350 2024-04-17 23:33 by petro
[有机交流] 怎么清洗烧瓶 20+5 ww34523 2024-04-16 6/300 2024-04-17 15:20 by 591950582
[论文投稿] 可以打电话问编辑部是否可以先发录用通知吗 +7 双倍好运锦鲤 2024-04-14 10/500 2024-04-17 13:38 by cjzhu
[基金申请] 请问教育部人文社科难度大吗 +9 锦衣卫寒战 2024-04-15 14/700 2024-04-16 23:10 by 锦衣卫寒战
[考研] 土木工程281求调剂 +4 乔兮木 2024-04-13 4/200 2024-04-16 21:40 by zjl渐行渐远
[基金申请] 迟国泰通过向学生发放劳务费再回收的方式套取科学基金重点项目 +6 babu2015 2024-04-13 7/350 2024-04-16 20:32 by sundiv
[考博] 24计算机申博 +4 学无止境er 2024-04-13 6/300 2024-04-16 19:15 by 学无止境er
[考研] 347求调剂 +3 寒辰ovo 2024-04-15 7/350 2024-04-16 19:05 by 寒辰ovo
[有机交流] 关于DMF +6 农药害害 2024-04-13 6/300 2024-04-16 15:57 by hwqMSE
[考研] 329求调剂 +6 Kaylawander 2024-04-13 7/350 2024-04-16 12:00 by 风来花开1
[考研] 329求调剂 +18 王郁洁哈哈哈 2024-04-14 26/1300 2024-04-15 19:10 by mumin1990
[考研] 328求调剂 +3 send rgsc 2024-04-14 7/350 2024-04-15 18:17 by zw_muchong
[有机交流] 求乙二醇检测方法 13+3 YaShang 2024-04-14 4/200 2024-04-15 15:16 by Byltest
[考研] 287求调剂 +6 南沨 2024-04-14 6/300 2024-04-14 23:08 by lincunhui
信息提示
关闭
请填处理意见
关闭