triangle_num=76576500
slow version, elapsed time=2.060000 seconds.
triangle_num=76576500
normal version, elapsed time=0.090000 seconds.

#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;
}

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 ...

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*2*3*3*5*5*5*7*11*13*17
76576500
>>> 2*2*3*3*5*5*5*67*251
75676500

f = factor(n) returns a row vector containing the prime factors of n.

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 ...

Originally posted by sudo at 2011-05-17 18:10:56:
这是两个不同的数嘛...

# -*- 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

Originally posted by holmescn at 2011-05-18 17:52:06:
虽然有了因数分解这个方法，可以快速的知道一个三角数有多少个整除数，但好像还只胡一个一个算，一个一个分解。这太慢了。

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

这就要求 ...

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 ...