How can I efficiently find all almost perfect numbers from 1 to n in C-CodePudding

I have been trying to find all almost perfect numbers between 1 and n in C.

I know that the the definition of an almost perfect number is that the sum of a number's divisors should equal that number -1.

My approach is that I iterate from 1 to that number, calculate the sum of its divisors, and then check if the sum is equal to that number -1 like in my code below.

int checkAlmoastPerfect(int n)
{
    int divisors = 0;

    for (int i = 1; i <=n; i  ) {

        if (n % i == 0)
            divisors  = i;
    }

    if (divisors == 2 * n - 1)
        return 1;

    return 0;
}

And it seems to work but it is rather slow. Checking 100 or 1000 numbers is not too bad, but if we go to something in the range of millions it takes a very long time, so after looking around I see that there is an approach that I do not need to check all numbers from 1 up to that number, but only up to the square root of that number.

So I change the for loop to this:

for (int i = 1; i <=sqrt(n); i  ) { ... }

and the check to this

if (divisors == n - 1)
        return 1;

But it doesn't work at all now: if I check the numbers from 1 to 100 I get that only 1, 2 and 4 are almost perfect numbers, which is wrong as there are a few more.

What have I done wrong here, and how can I make my original approach more efficient?

CodePudding user response：

it doesn't work at all now

The summation needs work too.

    //if (n % i == 0)
    //  divisors  = i;

    if (n % i == 0) {
      divisors  = i;
      if (i*i < n) divisors  = n/i;
    }

for (int i = 1; i < n/i; i  ) {
    if (n % i == 0)
        divisors  = i   n/i;
}
// look for perfect square
if (i == n/i) {
    if (n % i == 0)
        divisors  = i;
}

i <=sqrt(n); is dodgy to use FP here given sqrt() may only be weak and almost right. Best to use integer math for integer problems.

// for (int i = 1; i <=sqrt(n); i  ) { ... }
for (int i = 1; i <= n/i; i  ) { ... }

CodePudding user response：

Assuming that n is not super huge you could try calculate the sum of divisors for each number in range 1 to n at the same time. Rather that check if each number is divisible by d to increment its sum of divisors one can simply add d to the sum of divisors for number that are divisible by d. That leads to simple and efficient algorithm as below.

#include <stdlib.h>
#include <stdio.h>

int n = 10000;

int main() {
  int *sum = calloc(n   1, sizeof *sum);
  for (int d = 1; d <= n;   d)
    for (int p = 0; p <= n; p  = d)
      sum[p]  = d;

  // find number which sum of divisors (including itself) is 2n - 1
  for (int i = 0; i <= n;   i)
    if (sum[i] == i   i - 1)
       printf("%d\n", i);

  free(sum);
}

The program produces:

Powers of 2 are returned what is consistent with the current knowledge on "almost perfect numbers".

The complexity is:

n   n/2   n/3   .. = O(n * log(n))

No modulo nor division is needed though the algorithm is not very cache friendly.