求个算法。

大狗狗

UID: 19898
帖子: 1
积分: 2
在线时间: 10 分钟

1^# 大狗狗发表于 2009-01-04 22:15

求个算法。

F(n) = 1 + 2 + ,..., + n = (1+n)*n/2
求最小的n，使F(n)拥有超过500个的约数。

100的约数为（1，2，4，5，10，20，25，50，100）

我的垃圾新手写法。
@＠count=0
def yushu(num)
(1..num).each{|i| @@count+=1 if num%i == 0}
puts @@count
end
yushu(100)

大狗狗

UID: 19898
帖子: 1
积分: 2
在线时间: 10 分钟

2^# 大狗狗发表于 2009-01-04 22:17

额我理解这个题的意思是说求一个数字，它的约数应该有>=500个。

ly5066113

UID: 41125
帖子: 34
积分: 78
在线时间: 1 小时

3^# ly5066113 发表于 2009-01-05 11:04

[Copy to clipboard] [ - ]

CODE:

$ cat test.pl
#! /usr/bin/perl

use strict;
use warnings;

sub sum {
      my $sum = shift;

      $sum = (1 + $sum) * $sum / 2;

      return $sum;
}

sub yueshu {
      my $num = shift;
      my $max = $num;
      my $yueshu = 2;
      my $i = 2;

      while ( $i < $max )
      {
            if ( $num % $i == 0 )
            {
                     $max = $num / $i;
                     if ( $i == $max )
                     {
                              $yueshu ++;
                     }
                     else
                     {
                              $yueshu += 2;
                     }
            }

            $i ++;
      }

      return $yueshu;
}

my $num = 1;

while( yueshu(sum($num)) < 500 )
{
      $num ++;
}

print $num;
$ time test.pl
12375
real 0m51.475s
user 0m31.870s
sys    0m0.020s

MMMIX

UID: 31964
帖子: 137
积分: 315
在线时间: 1 天 1 小时

4^# MMMIX 发表于 2009-01-05 12:08

做的运算太多了。要是顺序求因数的话，只要求到原数的平方根就行了。当然也可以先将原数分解为质因数，然后用质因数的组合得到原数的所有因数。

大狗狗

UID: 19898
帖子: 1
积分: 2
在线时间: 10 分钟

5^# 大狗狗发表于 2009-01-05 12:16

QUOTE:

原帖由 ly5066113 于 2009-1-5 11:04 发表
$ cat test.pl
#! /usr/bin/perl

use strict;
use warnings;

sub sum {
      my $sum = shift;

      $sum = (1 + $sum) * $sum / 2;

      return $sum;
}

sub yueshu {
      m ...

def yueshu(num)
    count=0
    arr=[]
    (1..num).each  do  |i|
        count += 1 and  arr << i if  num%i ==0

        end

    return arr
end
puts yueshu(12375)

1
3
5
9
11
15
25
33
45
55
75
99
125
165
225
275
375
495
825
1125
1375
2475
4125
12375

你这个数字也没有500个约数阿。。。

大狗狗

UID: 19898
帖子: 1
积分: 2
在线时间: 10 分钟

6^# 大狗狗发表于 2009-01-05 12:18

QUOTE:

原帖由 MMMIX 于 2009-1-5 12:08 发表
做的运算太多了。要是顺序求因数的话，只要求到原数的平方根就行了。当然也可以先将原数分解为质因数，然后用质因数的组合得到原数的所有因数。

数学没有学好。这些概念都快忘记光了。。／

ly5066113

UID: 41125
帖子: 34
积分: 78
在线时间: 1 小时

7^# ly5066113 发表于 2009-01-05 12:19

我这个就是算到平方根呀。

ly5066113

UID: 41125
帖子: 34
积分: 78
在线时间: 1 小时

8^# ly5066113 发表于 2009-01-05 12:21

你题目要求的是n，拥有500个约数的是F(n)。
也就是 (1 + 12735) * 12735 / 2

ynchnluiti

UID: 39553
帖子: 24
积分: 55
在线时间: 10 分钟

9^# ynchnluiti 发表于 2009-01-05 13:10

QUOTE:

原帖由大狗狗于 2009-1-5 12:18 发表

数学没有学好。这些概念都快忘记光了。。／

我已经忘光了。

大狗狗

UID: 19898
帖子: 1
积分: 2
在线时间: 10 分钟

10^# 大狗狗发表于 2009-01-05 13:24

QUOTE:

原帖由 ly5066113 于 2009-1-5 12:21 发表
你题目要求的是n，拥有500个约数的是F(n)。
也就是 (1 + 12735) * 12735 / 2

约数的个数和n 有关系吗？

F(n)=1+2+..+n=(1+n)*n/2 这个和一个数所拥有的约数个数有关系吗？