Where is the error of that code?

Question

Exercise: Perform a procedure that returns, by parameter, a vector A(5) with the first 5 perfect numbers.

My Code:

#include <stdio.h>
#define TAM 5

void numeros_perfeitos(int A[]) {

    int cont = 0;
    int x, n = 1, soma;

    while (cont < TAM) {
        soma = 0;
        for (x = 1; x <= n; x++) {
            if (n % x == 0 && x != n) {
                soma += x;
            }
        }

        if (soma == n) {
            A[cont] = n;
            cont++;
        }

        n++;
    }
}   

int main () {

    int A[TAM];
    int cont;

    numeros_perfeitos(A);

    printf("Os primeiros cincos números perfeitos são: \n");

    for (cont = 0; cont < TAM; cont++) {
        printf("%d\n",A[cont]);
    }

    return 0;
}

Answer 1

I was looking here for an algorithm that would use the prime factors of the number to determine whether it is perfect or not, but I couldn’t find anything related. It must be because factoring and calculating divisors force the solution to create a combinatorial amount of numbers.

Perfect numbers

A number is said to be perfect if the sum of its own divisors is itself.

What is a separate divisor? For a number n, whichever d != n such that d > 0, d | n is a separate division of n. 1 has no own divisors; 2 has only 1 as its own divisor; 6 has 1, 2 and 3 as its own divisors.

Difficulty class of the problem

A point of interest to know if a solution will return result and what the expected time it returns the result is to know what the difficulty class of the problem.

Little by little. The classical classification (P, NP, PSPACE, RE and family) is about decision problems, which are those problems whose admissible answers are yes or nay. The problem perfection of number fits this definition because the number is perfect or not perfect.

There are several ways to classify problems, many of them are related to the type of computation/computational power used to solve it:

• limitation of running time
  • the class P implies that there is a solution that runs in polynomial (up) time for the size input problem n, that is, execution time in o(n^p);
  • the class EXP implies that there is a solution that runs in (up) exponential time for the size input problem n, that is, running time o(e^(n^p)); P belongs to EXP, because o(n^p) < o(e^n) < o(e^(n^p));
• limitation of available memory space
  • the PSPACE class implies that for a size input n, there is a solution that requires as much as possible o(n^p) extra working memory; class P is contained in its own way within PSPACE; PSPACE is contained within EXP (if it can be placed in every position X distinct symbols, traversing all combinations in memory takes time X^(o(n^p)) = o(e^(n^p)))
• limitation by determinism
  • the class P is relative to problems that are solved in polynomial time by a deterministic algorithm;
  • the class NP is relative to problems that are solved in polynomial time by a nondeterministic algorithm;

A feature of the NP class is that it is possible to simulate a nondeterministic operation given the problem is also a tip what the next step to take at the time of nondeterminism. To this tip is named after certified. To simulate an NP computational power, we need to deliver a certificate with at most one symbol for each computation step; i.e., the maximum certificate size is o(n^p), where n is the size of the input.

Given the input and a certificate for it, we need a deterministic algorithm to prove that the answer is correct. Given this, we have been able to prove that a problem is NP.

I thought the following certificate for the perfect number problem: - prime factors and their multiplicities (for example, entry 496, prime factors [2,4] [31,1]) - the o(n^0.5) dividers of n (value that is identical to the product of the multiplicity of primes + 1; for 496, we have (4+1) x (2 + 1) = 10 divisors)

About number of divisors, has a note in that reply who has proof that it is o(2 * n^0.5) ==> o(n^0.5) for a number n

The size of this certificate is polynomial, so the first requirement was met. To verify that the certificate is valid, we have the following steps:

• add the supposed splitters and ensure that the result is 2n, because the sum of the own divisors is n and the very n also entered the list of past dividers
• ensure that the amount of splitters follows the product formula of multiplicities + 1; verification is done quickly
• ensure that all supposed splitters are de facto splitters
• divide the number by its prime factors and get 1 at the end

With this, we have that the certificate is valid and the number with that certificate is perfect. Unfortunately, I can’t tell you the complexity of the division, but I think it’s quadratic. So in this case, we have that the running time of the algorithm that validates the certificate is also polynomial.

I cannot prove that the problem is P, however. If NP != P, and this problem is not P, so we can’t solve in polynomial time, but we can try to decrease the amount of operations performed.

Algorithm to find all splitters

To find the amount of divisors of a number, we need to go from 2 to the square root of the number (as demonstrated in this reply). 1 is already divisor of any number, so there is no need to compute it. For each number D splitter found, we have N/D like the other divider. Doing the division operation once and storing the quotient and the rest, we can verify if the number is the same divisor and, unlike the example, add the two sibling factors. Just remembering that the whole square root case only counts once as splitter.

In C

int soma_divisores(int n) {
  int sq = sqrt(n);
  int i;
  int f;
  int soma = 1; // 1 divide todo mundo
  for (i = 2; i < sq; i++) {
    // se achei um número divisor, achei outro também 
    if (n % i == 0) {
      f = n/i;
      soma += f + i;
    }
  }

  // testando se é quadrado perfeito
  if (sq * sq == n) {
    soma += sq;
  }

  return soma;
}

As the splitter search space has been abruptly broken, this code should run much faster on your machine.

Answer 2

The error is no while it does not run as it is always less than zero try to change