gpt4 book ai didi

c# - 如何加快 Amicable 号码算法的速度?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:05:34 24 4
gpt4 key购买 nike

完成 100,000 的限制(n)需要相当长的时间。

我怀疑问题出在 CalculateAmicable() 上,其中数字变大并且需要更多时间来计算。我可以更改什么以使其速度比这更快?

public static void Main (string[] args)
{
CheckAmicable (1, 100000);

}

public static int CheckAmicable(int start, int end)
{
for (int i = start; i < end; i++) {

int main = CalculateAmicable (i); //220
int temp = CalculateAmicable (main); //284
int compare = CalculateAmicable (temp); //220
if (compare == main) {
if (main != temp && temp == i) {
Console.WriteLine (main + " = " + temp + " = " + compare + " i: " + i);
i = compare + 1;
}
}
}
return 0;
}

public static int CalculateAmicable(int number)
{
int total = 0;
for (int i = 1; i < number; i++) {
if (number%i == 0){
total += i;
}
}
return total;
}

注意:英语不是我的母语!

最佳答案

是的,CalculateAmicable低效 - O(N) 复杂度 - 所以你有 fo N 测试1e5 * 1e5 == 1e10 - 百亿 操作很慢。将复杂度降低到 O(log(N)) 的方案是

  int n = 100000;

//TODO: implement IList<int> GetPrimesUpTo(int) yourself
var primes = GetPrimesUpTo((int)(Math.Sqrt(n + 1) + 1));

// Key - number itself, Value - divisors' sum
var direct = Enumerable
.Range(1, n)
.AsParallel()
.ToDictionary(index => index,
index => GetDivisorsSum(index, primes) - index);

var result = Enumerable
.Range(1, n)
.Where(x => x < direct[x] &&
direct.ContainsKey((int) direct[x]) &&
direct[(int) direct[x]] == x)
.Select(x => $"{x,5}, {direct[x],5}");

Console.Write(string.Join(Environment.NewLine, result));

结果在一秒钟之内(Core i7 3.2Ghz .Net 4.6 IA-64):

  220,   284
1184, 1210
2620, 2924
5020, 5564
6232, 6368
10744, 10856
12285, 14595
17296, 18416
63020, 76084
66928, 66992
67095, 71145
69615, 87633
79750, 88730

详细信息GetDivisorsSum:

private static long GetDivisorsSum(long value, IList<int> primes) {
HashSet<long> hs = new HashSet<long>();

IList<long> divisors = GetPrimeDivisors(value, primes);

ulong n = (ulong) 1;
n = n << divisors.Count;

long result = 1;

for (ulong i = 1; i < n; ++i) {
ulong v = i;
long p = 1;

for (int j = 0; j < divisors.Count; ++j) {
if ((v % 2) != 0)
p *= divisors[j];

v = v / 2;
}

if (hs.Contains(p))
continue;

result += p;

hs.Add(p);
}

return result;
}

GetPrimeDivisors:

private static IList<long> GetPrimeDivisors(long value, IList<int> primes) {
List<long> results = new List<long>();

int v = 0;
long threshould = (long) (Math.Sqrt(value) + 1);

for (int i = 0; i < primes.Count; ++i) {
v = primes[i];

if (v > threshould)
break;

if ((value % v) != 0)
continue;

while ((value % v) == 0) {
value = value / v;

results.Add(v);
}

threshould = (long) (Math.Sqrt(value) + 1);
}

if (value > 1)
results.Add(value);

return results;
}

关于c# - 如何加快 Amicable 号码算法的速度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41653159/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com