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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler Project Q12 欧拉工程第十二题
242/3返回列表上一页123下一页
查看: 3548  |  回复: 23
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 7 个 程序强帖 ，点击这里进行查看

wangww2011

木虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2, 程序强帖+1): 谢谢参与交流！ 2011-05-17 22:30:26
楼上的分析的很多阿
还是直接写代码吧
最简单就是遍历了，其实也不是很慢，2秒多一点
优化一下也没有快多少，0.1s
先看运行结果
CODE:
triangle_num=76576500
slow version, elapsed time=2.060000 seconds.
triangle_num=76576500
normal version, elapsed time=0.090000 seconds.

代码：
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 euler12(int a, long n){
  static int last_a=0;
  static int count=1;
  int tmp_count=0;
  int i=0;
  
  for(i=a;i     if(n%i==0){
      if(i>last_a){
         last_a=i;
         tmp_count=count;
         count=2;
         return tmp_count*euler12(i,n/i);
       }
      
       count++;      
       return euler12(i,n/i);
    }
  }


  tmp_count=count;
  count=1;
  last_a=0;

  if (i*i-n==0){
    return 3*tmp_count;
  } else {
    return 2*tmp_count;
  }
}



int slow(int n){
  int i=0;
  int count=0;
  for(i=2;i<=sqrt(n);i++){
    if(n%i==0){
      count++;
     }
  }

  if (i*i-n==0) {
    return 2*count+1;
  }

  return 2*(count+1);
}


int main(void){
  long triangle_num=1;
  int i=2;
  int divisor_num=500;
  

  TIMERSTART;

  do {
    triangle_num+=i;
    i+=1;
  }while(slow(triangle_num)
  printf("triangle_num=%ld\n slow version, ",triangle_num);
  TIMERSTOP;



  start_time = clock();  
  triangle_num=1;
  i=2;

  do {
    triangle_num+=i;
    i+=1;
  }while(euler12(2,triangle_num)
  printf("triangle_num=%ld\n normal version, ",triangle_num);
  TIMERSTOP;

  return 0;
}
赞一下(2人) 回复此楼
11楼2011-05-17 16:04:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-17 22:30:42
引用回帖:
Originally posted by libralibra at 2011-05-17 15:55:18:
sudo兄7楼的算法再解释下?
>> factor(75676500)
ans =
     2     2     3     3     5     5     5    67   251

照此,75676500 = 2^2*3^2*5^3*67^1*251^1
它的因子个数是 3*3*4*2*2 = 144,也不是50 ...

我算的是  76576500
76576500=2*2*3*3*5*5*5*7*11*13*17
所以应该有3*3*4*2*2*2*2=576个因数
赞一下(2人) 回复此楼
12楼2011-05-17 16:11:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
余泽成(金币+2): 谢谢参与交流！ 2011-05-17 22:30:52
引用回帖:
Originally posted by wangww2011 at 2011-05-17 16:11:33:
我算的是  76576500
76576500=2*2*3*3*5*5*5*7*11*13*17
所以应该有3*3*4*2*2*2*2=576个因数

好奇怪啊,2个分解质因数都对,这不是与唯一分解定理矛盾了吗?

matlab的factor怎么会给出第2个呢?
CODE:
>>> 2*2*3*3*5*5*5*7*11*13*17
76576500
>>> 2*2*3*3*5*5*5*67*251
75676500

这是factor的解释
CODE:
f = factor(n) returns a row vector containing the prime factors of n.
赞一下(1人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
13楼2011-05-17 17:50:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by libralibra at 2011-05-17 17:50:36:
好奇怪啊,2个分解质因数都对,这不是与唯一分解定理矛盾了吗?

matlab的factor怎么会给出第2个呢?

[code] >>> 2*2*3*3*5*5*5*7*11*13*17
76576500
>>> 2*2*3*3*5*5*5*67*251
7567650 ...

这是两个不同的数嘛...
赞一下(1人) 回复此楼
14楼2011-05-17 18:10:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
引用回帖:
Originally posted by sudo at 2011-05-17 18:10:56:
这是两个不同的数嘛...

哈哈,多谢提醒,我当时保存答案的时候是手写的,写错了数字
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
15楼2011-05-17 18:15:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励参与交流！ 2011-05-19 19:16:20
CODE:
# -*- coding: utf-8 -*-

# 初始化一个质数表
i = 0
primes = range(2, 100)
while i < len(primes):
    primes = [x for x in primes if x == primes[i] or x % primes[i] != 0]
    i = i + 1

def numbersOfFactors(n):
    """计算n的因子数
    使用了sudo说的计算方法
    加上一个质数分解
    """
    factorNumbers = 1
    factorTimes = 0
    i = 0
    while i < len(primes):
        if n % primes[i] == 0:
            factorTimes += 1
            n /= primes[i]
            continue
        else:
            if factorTimes != 0:
                factorNumbers *= factorTimes + 1
                factorTimes = 0
            i = i + 1
            if n == 1:
                break
    return factorNumbers

# 从第三个三角数开始算，只算第奇数个三角数
n = 3
while numbersOfFactors(n*(n+1)/2) < 500:
    n += 2

# 为防止对偶数个三角数的遗漏，有最后这个计算
if numbersOfFactors(n*(n-1)/2) > 500:
    print n*(n-1)/2
else:
    print n*(n+1)/2

写了个质数分解版的。速度是很快啊！

[ Last edited by holmescn on 2011-5-19 at 16:34 ]
赞一下(2人) 回复此楼
16楼2011-05-18 17:52:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

baiyuefei

版主 (文学泰斗)

风雪

优秀版主优秀版主优秀版主文献杰出贡献优秀版主优秀版主优秀版主文献杰出贡献优秀版主优秀版主优秀版主优秀版主文献杰出贡献优秀版主优秀版主优秀版主优秀版主优秀版主优秀版主
帮顶
回复此楼
17楼2011-05-18 18:59:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+1): 鼓励参与交流！ 2011-05-19 19:16:36
引用回帖:
Originally posted by holmescn at 2011-05-18 17:52:06:
虽然有了因数分解这个方法，可以快速的知道一个三角数有多少个整除数，但好像还只胡一个一个算，一个一个分解。这太慢了。

显然第n个三角数就是n(n+1)/2。令这个数为a则可以解得n=(sqrt(8a+1)-1)/2

这就要求 ...

辗转相除法可以计算gcd，计算完之后两边再单独分解即可。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
18楼2011-05-18 19:48:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

匿名

用户注销 (小有名气)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励交流！欢迎常来程序语言版！ 2011-05-24 12:36:56
本帖仅楼主可见
赞一下
19楼2011-05-24 09:00:01
已阅   回复此楼   编辑   查看我的主页

holmescn

金虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by fan6cy at 2011-05-24 09:00:01:
首先列出matlab计算的结果和时间：
y =

    76576500


time =

    4.5780
如果你觉得我的程序还不错，请继续往下看：
本程序一共有三个程序组成，fibon.m,nfactor.m,ruler12.m
fibon.m
function y ...

推荐使用BBCode重新编辑你的代码，让代码更好看，更易读。
赞一下(1人) 回复此楼
20楼2011-05-24 09:51:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 libralibra 的主题更新
242/3返回列表上一页123下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭