求个算法。

ly5066113

晕死啊，题目是你出的啊！你还没读懂？
n=1  F(n)=1
n=2  F(n)=3
n=3  F(n)=6
......
n=12735 F(n)=81096480

要求的是最小的n，使得F(n)有500个约数。

可以看到F(n)是一个不连续的数列，所以你2楼的说法是不对的，最小的拥有500个约数的数字，不一定是F(n)中的一个。

大狗狗

原帖由 ly5066113 于 2009-1-5 13:35 发表
晕死啊，题目是你出的啊！你还没读懂？
n=1  F(n)=1
n=2  F(n)=3
n=3  F(n)=6
......
n=12735 F(n)=81096480

要求的是最小的n，使得F(n)有500个约数。

可以看到F(n)是一个不连续的数列，所以你2楼的 ...

这个我明白。只是我想知道  F(n) 的公约数的个数和 n的关系。应该是没有关系的 ，f(n) -->n  这个是有关系的。

那么我就是想知道 f(n) 例如 f(100)的公约数的个数 有啥好的求法。

ly5066113

就是我代码里的 sub yueshu 这个子函数呀。

首先1和这个数本身一定是它的约数，所以从2开始查找它的约数，一直找到它的平方根为止。
对与完全平方数，我的代码是没问题的，非完全平方数是多做了一些计算的。

ly5066113

改进版：

1. #! /usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. sub yueshu {
   
7.         my $num = shift;
   
8.         my $max = int(sqrt($num));
   
9.         my $yueshu = 2;
   
10.         my $i = 2;
    
11. 
    
12.         while ( $i <= $max )
    
13.         {
    
14.                 if ( $num % $i == 0 )
    
15.                 {
    
16.                         if ( $i == $max )
    
17.                         {
    
18.                                 $yueshu ++;
    
19.                         }
    
20.                         else
    
21.                         {
    
22.                                 $yueshu += 2;
    
23.                         }
    
24.                 }
    
25. 
    
26.                 $i ++;
    
27.         }
    
28. 
    
29.         return $yueshu;
    
30. }
    
31. 
    
32. print yueshu(100);

复制代码

MMMIX

原帖由 ly5066113 于 2009-1-5 12:19 发表
我这个就是算到平方根呀。

哦，是我没看太仔细。

大狗狗

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

(1 + 12735) * 12735 / 2=81096480

=2^5*3^2*5^1*199^1*283^1

(5+1)*(2+1)*(1+1)*(1+1)*(1+1)=144 这个数应该有144个约数


而不是>500个约数。

ly5066113

晕，写错了，应该是：

(1 + 12375) * 12375 / 2 = 76576500

大狗狗

原帖由 ly5066113 于 2009-1-6 17:21 发表
晕，写错了，应该是：

(1 + 12375) * 12375 / 2 = 76576500

32672640
18378360

我这里随便2个数字 都比你的小  却有512个约数。

ly5066113

这就说明你还没理解题目。
32672640 不是 F(n) 中的一个呀。

大狗狗

原帖由 ly5066113 于 2009-1-6 18:00 发表
这就说明你还没理解题目。
32672640 不是 F(n) 中的一个呀。

SORRY 看来是我的理解错误了。

我是想求一个最小数字 它的约数一定要大于或者等于500 。。

看来我是瞎折腾来着／／／

puts yueshu（2＊3＊5＊7＊11＊13＊19＊21）

把约数的个数求法仔细研究。结果还是没有个规律。

不钻这个牛角了