Abundant, deficient and perfect number classifications: Difference between revisions
Abundant, deficient and perfect number classifications (view source)
Revision as of 22:01, 29 November 2021
, 2 years ago→{{header|C sharp}}: added third method to comparison, added performance comparison.
m (→{{header|Python}}: Doh! No sense checking factors > n / 2.) |
(→{{header|C sharp}}: added third method to comparison, added performance comparison.) |
||
Line 1,763:
=={{header|C sharp}}==
Three algorithms presented, the first is fast, but can be a memory hog when tabulating to larger limits. The second is slower, but doesn't have any memory issue. The third is quite a bit slower, but the code may be easier to follow.
First method:
:Initializes a large queue, uses a double nested loop to populate it, and a third loop to interrogate the queue.<br>
Second method:
:Uses a double nested loop with the inner loop only reaching to sqrt(i), as it adds both divisors at once, later correcting the sum when the divisor is a perfect square.
Third method:
:Uses a loop with a inner Enumerable.Range reaching to i / 2, only adding one divisor at a time.
<lang csharp>using System;
using System.Linq;
Line 1,771 ⟶ 1,779:
{
int abundant, deficient, perfect;
var sw = System.Diagnostics.Stopwatch.StartNew();
ClassifyNumbers.UsingSieve(20000, out abundant, out deficient, out perfect);▼
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");
ClassifyNumbers.UsingDivision(20000, out abundant, out deficient, out perfect);
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");
}
}
Line 1,781 ⟶ 1,793:
public static class ClassifyNumbers
{
//Fastest way, but uses memory
public static void UsingSieve(int bound, out int abundant, out int deficient, out int perfect) {
//For very large bounds, this array can get big.
int[] sum = new int[bound + 1];
for (int divisor = 1; divisor <= bound
for (int i = divisor
sum[i] += divisor;
}▼
}▼
for (int i = 1; i <= bound; i++) {
if (sum[i]
else if (sum[i]
▲ else p++;
}
deficient = d;▼
▲ perfect = p;
}
//
public static void UsingOptiDivision(int bound, out int abundant, out int deficient, out int perfect) {
for (int i = 2, d, r = 1; i <= bound; i++) {
if ((d = r * r - i) < 0) r++;
for (int x = 2; x < r; x++) if (i % x == 0) sum += x + i / x;
if (d == 0) sum += r;
switch (sum.CompareTo(i)) { case 0: perfect++; break; case 1: abundant++; break; }
▲ }
▲ }
//Much slower, doesn't use storage and is un-optimized
public static void UsingDivision(int bound, out int abundant, out int deficient, out int perfect) {
for (int i =
int sum = Enumerable.Range(1, (i + 1) / 2)
.Where(div =>
▲ }
}
▲ deficient = d;
▲ perfect = p;
}
}</lang>
{{out|Output @ Tio.run}}
We see the second method is about 10 times slower than the first method, and the third method more than 120 times slower than the second method.
<pre>
Abundant: 4953, Deficient: 15043, Perfect: 4 0.7277 ms
Abundant: 4953, Deficient: 15043, Perfect: 4 7.3458 ms
Abundant: 4953, Deficient: 15043, Perfect: 4 1048.9541 ms
</pre>
| |||