B

I was looking for an algorithm that used the prime factors of the number to determine whether it is perfect or not, but I did not find anything related. It should be because factoring and calculating the divisors force the solution to create a combinatory number amount.Perfect numbersA number is said perfect if the sum of your own dividers is himself.What is a splitter of its own? For a number n, any d != n such as d > 0, d | n is a splitter own n. 1 has no own dividers; 2 has only 1 as its own divider; 6 has 1, 2 and 3 as own dividers.Problem difficulty classA 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.Just a few. Classical classification (P, NP, PSPACE, RE and family) is about decision problems, which are those problems whose admissible answers are Yes or No. The problem perfection of number fits this definition, as the number is perfect or is not perfect.There are several ways to sort the problems, many of them are related to the type of computing/computational power used to solve it:limitation of runtimethe class P implies that there is a solution that runs in polynomial time to the size input problem n, i.e. runtime in o(n^p);the EXP class implies that there is a solution that runs in time (even) exponential for the size input problem n, i.e. runtime o(e^(n^p)); P belongs to EXP, for o(n^p) < o(e^n) < o(e^(n^p));memory space limitation availablethe PSPACE class implies that, for a size entry n, there is a solution that requires maximum o(n^p) extra working memory; class P is contained in its own way within PSPACE; PSPACE is contained within EXP (if you can put in any position X distinctive symbols, go through all combinations in memory takes time X^(o(n^p)) = o(e^(n^p)))limitation by determinismthe class P is related to problems that are solved in polynomial time by a deterministic algorithm;the NP class is related 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 non-deterministic operation given the problem is also a tip of which the next step to follow at the time of non-determinism. To that tip is given the name certificate. To simulate an NP computational power, we need to deliver a certificate with at most a symbol for each computing step; that is, the maximum size of the certificate is o(n^p), where n is the size of the entrance.Given the input and a certificate for it, we need a deterministic algorithm to prove that the answer is correct. Given that, we can prove that a problem is NP.I thought of the following certificate for the perfect number problem:
- prime factors and their multiplicities (e.g. input 496, prime factors [2.4] ; [31,1])
- o(n^0.5) divisors n (value that is identical to the product of the multiplicities of primes + 1; for 496, we have (4+1) x (2 + 1) = 10 dividers)About how many divisor numbers, have https://pt.stackoverflow.com/a/209275/64969 who has proof that it is o(2 * n^0.5) ==> o(n^0.5) for a number nThe size of this certificate is polynomial, so the first question was satisfied. To verify that the certificate is valid, we have the following steps:add the supposed dividers and ensure that the result is 2n, for the sum of the own dividers is n and itself n also entered the list of past dividersensure that the amount of splitters follow the product formula of multiplicities + 1; check this made quicklyensure all supposed dividers are indeed dividerssplit the number by your prime factors and get 1 in the endWith this, we have the certificate valid and the number with this certificate is perfect. Unfortunately, I do not know what the complexity of the division is, but I think it is. https://en.m.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations . Thus, in this case, we have to run the algorithm that validates the certificate is polynomial too.I can't prove the problem is P, though. If NP != P, and this problem is not P, then we cannot solve in polynomial time, but we can try to decrease the amount of operations carried out.Algorithm to find all dividersTo find the amount of divisors of a number, we need to go from 2 to the square root of the number (as shown in this https://pt.stackoverflow.com/a/209275/64969 ). 1 is already a splitter of any number, so you do not have to compute it. For each number D divisor found, we have N/D like the other divider. Once the division operation and storing the quotient and the rest, we can verify whether the number is splitter even and, unlike the example, add the two fraternal factors. Just remembering that the whole square root case only counts once as splitter.In Cint 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 divisor search space was abruptly broken, this code should run much faster on your machine.