33,008
社区成员
发帖
与我相关
我的任务
分享关于小于n的亲和数的线性求法，To：v_JULY_v
Blog实在没法写，还是专门开一个帖子吧！
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)
比如2*3*5*7的约数和 = 3*4*6*8
设f(n)是n的所有约数的和，有了上面的递推，算90这样的数的约数和时，没有必要把1、2、3、5、6、9、10、15、18、30、45、90都加一遍，f(90) = f(45) * 3，因此把质数的线性筛法改一下，就可以了。
当然很有可能还有更好的方法，如果有构造的可能的话，也许效率会非常高，我就当抛砖引玉了。
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)
比如2*3*5*7的约数和 = 3*4*6*8
设f(n)是n的所有约数的和，有了上面的递推，算90这样的数的约数和时，没有必要把1、2、3、5、6、9、10、15、18、30、45、90都加一遍，f(90) = f(45) * 3，因此把质数的线性筛法改一下，就可以了。
当然很有可能还有更好的方法，如果有构造的可能的话，也许效率会非常高，我就当抛砖引玉了。
using System;
using System.Collections.Generic;
namespace CSharpTest
{
class Program
{
public static void Main()
{
int max = 5000000;
int[] counter = CreateCounter(max);
for (int i = 0; i < counter.Length; i++)
{
int num = counter[i] - i;
if (num < counter.Length && num > i && counter[num] == counter[i])
Console.WriteLine("{0} {1}", i, num);
}
Console.ReadKey();
}
static int[] CreateCounter(int n)
{
List<int> primes = new List<int>();
int[] counter = new int[n + 1];
counter[1] = 1;
for (int i = 2; i <= n; i++)
{
if (counter[i] == 0)
{
counter[i] = i + 1;
primes.Add(i);
}
for (int j = 0; j < primes.Count; j++)
{
if (primes[j] * i > n)
break;
if (i % primes[j] == 0)
{
int k = i;
int l = primes[j] * primes[j];
while (k % primes[j] == 0)
{
l *= primes[j];
k /= primes[j];
}
counter[primes[j] * i] = counter[k] * (l - 1) / (primes[j] - 1);
break;
}
else
counter[primes[j] * i] = counter[i] * (primes[j] + 1);
}
}
return counter;
}
}
}
...全文
请发表友善的回复…
发表回复
TKD03072010 2011-05-29
- 打赏
- 举报
呵 学习了 ，博客上看了一下，哎 发现自己的差距越来越遥远咯！！！！！
超级大笨狼 2011-05-29
- 打赏
- 举报
真因子不是质数吗？4不是质数啊？
超级大笨狼 2011-05-29
- 打赏
- 举报
这个东西有什么用途？
pandm 2011-05-27
- 打赏
- 举报
表示看不懂。。。路过并膜拜一下大牛们。。。。
q107770540 2011-05-27
- 打赏
- 举报
mark一下
天下第一好大人 2011-05-27
- 打赏
- 举报
先顶再看，那天看了你说线性复杂度以后，特意去看了线性质数筛法的代码。可是还是没想出来怎么弄。原来是有这个质因子的性质做桥梁，佩服！
孤独小剑 2011-05-27
- 打赏
- 举报
这是什么约数和？
绿色夹克衫 2011-05-27
- 打赏
- 举报
转一下july的Blog，说明一下题意，怕大家看不明白
亲和数问题最早是由毕达哥拉斯学派发现和研究的。他们在研究数字的规律的时候发现有以下性质特点的两个数：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而这两个数恰恰等于对方的真因子各自加起来的和（sum[i]表示数i 的各个真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。
现在的目标就是找出500万以内的亲和数。
[Quote=引用 8 楼 pandm 的回复:]
表示看不懂。。。
[/Quote]
亲和数问题最早是由毕达哥拉斯学派发现和研究的。他们在研究数字的规律的时候发现有以下性质特点的两个数：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而这两个数恰恰等于对方的真因子各自加起来的和（sum[i]表示数i 的各个真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。
现在的目标就是找出500万以内的亲和数。
[Quote=引用 8 楼 pandm 的回复:]
表示看不懂。。。
[/Quote]
绿色夹克衫 2011-05-26
- 打赏
- 举报
说速度的话，这个方法未必比n*log(n)的快，一般来讲由于缓存命中的问题，线性筛法的速度比不上那个n*log(log(n))的厄氏筛法。只是算法的复杂度，这种方法会比较低。
[Quote=引用 4 楼 v_july_v 的回复:]
0.484375
0.484375
0.46875
单位second
[/Quote]
[Quote=引用 4 楼 v_july_v 的回复:]
0.484375
0.484375
0.46875
单位second
[/Quote]
v_JULY_v 2011-05-26
- 打赏
- 举报
[Quote=引用 4 楼 v_july_v 的回复:]
引用楼主 litaoye 的回复:
Blog实在没法写，还是专门开一个帖子吧！
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)……
[/Quote]
#include "time.h"
#include "stdio.h"
#include "stdlib.h"
time_t c_start,t_start, c_end,t_end;
c_start = clock();
c_end = clock();
printf("The program used %f ms by time().\n",difftime(c_end,c_start)) ;
引用楼主 litaoye 的回复:
Blog实在没法写，还是专门开一个帖子吧！
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)……
[/Quote]
#include "time.h"
#include "stdio.h"
#include "stdlib.h"
time_t c_start,t_start, c_end,t_end;
c_start = clock();
c_end = clock();
printf("The program used %f ms by time().\n",difftime(c_end,c_start)) ;
v_JULY_v 2011-05-26
- 打赏
- 举报
[Quote=引用楼主 litaoye 的回复:]
Blog实在没法写，还是专门开一个帖子吧！
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)
比如2*3*5*7的约数和 =……
[/Quote]
0.484375
0.484375
0.46875
单位second
Blog实在没法写，还是专门开一个帖子吧！
思路也比较简单
设n = p1^a1 * p2^a2 * .... pn^an(p1-pn为因数分解，a1-an为幂)，则n的所有约数和 = (p1^(a1+1) - 1) * (p2^(a2+1) - 1) * .... (pn^(an+1) - 1)/(p1-1)(p2-1).......(pn-1)
比如2*3*5*7的约数和 =……
[/Quote]
public static void Main()
{
int max = 5000000;
DateTime start = DateTime.Now;
int[] counter = CreateCounter(max);
for (int i = 0; i < counter.Length; i++)
{
int num = counter[i] - i;
//if (num < counter.Length && num > i && counter[num] == counter[i])
// Console.WriteLine("{0} {1}", i, num);
}
Console.WriteLine((DateTime.Now - start).TotalSeconds);
Console.ReadKey();
}0.484375
0.484375
0.46875
单位second
liuzhengxi2010 2011-05-26
- 打赏
- 举报
学习学习
KeyCw88 2011-05-26
- 打赏
- 举报
接分，学习~
v_JULY_v 2011-05-26
- 打赏
- 举报
