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

24小时热门版块排行榜    

CyRhmU.jpeg
小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三题：寻找600851475143的最大质因子
71/1返回列表
查看: 3629  |  回复: 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返回列表
普通表情 龙 兔 虎 猫 高级回复(可上传附件)
信息提示
关闭
请填处理意见
关闭