Abundant, deficient and perfect number classifications: Difference between revisions

Content added Content deleted
m (→‎{{header|Python}}: Doh! No sense checking factors > n / 2.)
(→‎{{header|C sharp}}: added third method to comparison, added performance comparison.)
Line 1,763: Line 1,763:


=={{header|C sharp}}==
=={{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;
<lang csharp>using System;
using System.Linq;
using System.Linq;
Line 1,771: Line 1,779:
{
{
int abundant, deficient, perfect;
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}");
ClassifyNumbers.UsingSieve(20000, out abundant, out deficient, out perfect); sw.Stop();
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");

⚫
sw.Restart();
⚫
ClassifyNumbers.UsingOptiDivision(20000, out abundant, out deficient, out perfect);
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");
⚫
sw.Restart();
ClassifyNumbers.UsingDivision(20000, out abundant, out deficient, out perfect);
ClassifyNumbers.UsingDivision(20000, out abundant, out deficient, out perfect);
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect}");
Console.WriteLine($"Abundant: {abundant}, Deficient: {deficient}, Perfect: {perfect} {sw.Elapsed.TotalMilliseconds} ms");
}
}
}
}
Line 1,781: Line 1,793:
public static class ClassifyNumbers
public static class ClassifyNumbers
{
{
//Fastest way
//Fastest way, but uses memory
public static void UsingSieve(int bound, out int abundant, out int deficient, out int perfect) {
public static void UsingSieve(int bound, out int abundant, out int deficient, out int perfect) {
int a = 0, d = 0, p = 0;
abundant = perfect = 0;
//For very large bounds, this array can get big.
//For very large bounds, this array can get big.
int[] sum = new int[bound + 1];
int[] sum = new int[bound + 1];
for (int divisor = 1; divisor <= bound / 2; divisor++) {
for (int divisor = 1; divisor <= bound >> 1; divisor++)
for (int i = divisor + divisor; i <= bound; i += divisor) {
for (int i = divisor << 1; i <= bound; i += divisor)
sum[i] += divisor;
sum[i] += divisor;
⚫
}
⚫
}
for (int i = 1; i <= bound; i++) {
for (int i = 1; i <= bound; i++) {
if (sum[i] < i) d++;
if (sum[i] > i) abundant++;
else if (sum[i] > i) a++;
else if (sum[i] == i) perfect++;
⚫
else p++;
}
}
abundant = a;
deficient = bound - abundant - perfect;
⚫
deficient = d;
⚫
perfect = p;
}
}

⚫
//Much slower, but doesn't use storage
//Slower, optimized, but doesn't use storage
public static void UsingOptiDivision(int bound, out int abundant, out int deficient, out int perfect) {
⚫
abundant = perfect = 0; int sum = 0;
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; }
⚫
sum = 1;
⚫
}
⚫
deficient = bound - abundant - perfect;
⚫
}

//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) {
public static void UsingDivision(int bound, out int abundant, out int deficient, out int perfect) {
int a = 0, d = 0, p = 0;
abundant = perfect = 0;
for (int i = 1; i < 20001; i++) {
for (int i = 2; i <= bound; i++) {
int sum = Enumerable.Range(1, (i + 1) / 2)
int sum = Enumerable.Range(1, (i + 1) / 2)
.Where(div => div != i && i % div == 0).Sum();
.Where(div => i % div == 0).Sum();
if (sum < i) d++;
switch (sum.CompareTo(i)) {
else if (sum > i) a++;
case 0: perfect++; break;
else p++;
case 1: abundant++; break;
⚫
}
}
}
abundant = a;
deficient = bound - abundant - perfect;
⚫
deficient = d;
⚫
perfect = p;
}
}
}</lang>
}</lang>
{{out}}
{{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>
<pre>
Abundant: 4953, Deficient: 15043, Perfect: 4
Abundant: 4953, Deficient: 15043, Perfect: 4 0.7277 ms
Abundant: 4953, Deficient: 15043, Perfect: 4
Abundant: 4953, Deficient: 15043, Perfect: 4 7.3458 ms
Abundant: 4953, Deficient: 15043, Perfect: 4 1048.9541 ms
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Abundant,_deficient_and_perfect_number_classifications"