1. Concept
First, let’s understand what perfect number is?
Problem Description: If a natural number, the sum of all its true factors (i.e., divisors other than itself) is exactly equal to it, and this number is called a complete number. Abbreviated as "finished number"
For example,
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064
According to the definition of the finished number, it is not too difficult to solve the number using the program. First, solve all the true factors of this number, then add them to determine whether it is equal to it. However, when this number is very small, there is no problem. Once this number exceeds a certain value, the problem arises and the execution efficiency of the program will become insulted.
When we optimize the algorithm logic of programs, we often consider a question: how to efficiently utilize the characteristics of computers? Are there a lot of repeated useless work in the algorithm it defines? By considering this problem along this line of thinking, we will soon get another solution.
2. Description
2.1 Analysis
Here, will we easily think of the decomposition factor we mentioned before? Yes, when solving perfect numbers, we will use decomposition factors. Generally speaking, solving a perfect number will go through three steps:
1. Find a certain number of prime numbers
2. Use the prime number table to find the factorization of the specified number
3. Use factorization to find all true factors and check whether it is a perfect number
2.2 Difficulties
After a first look, there is no problem with the first and second steps. We have discussed it in the previous two articles. Students who are not clear about it can check it out.
The key point is in the third step, how to find the true factor sum? The method is very simple. You must first know that adding all the true factors (students who don’t know the concept of true factors, go and have a look) and add the number itself will be twice the number (some students don’t know, but they should know it now, right?), for example:
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28
In fact, this equation can be converted to: (Code input error, I used screenshots)
Discovered? 2 and 7 are both factorized, so is there a simplification of the program?
2.3 Conclusion
Only factorization is required, and you can use a loop to find the value after the equation, and divide the value by 2 to be the true factor sum; when you first look at the equation, you may think of using the equation series formula to solve it, but you will use the power operation. You can calculate the value after the equation at the same time when reading the factorization array.
3. Code
import java.util.ArrayList; // Solve the perfect number public class PerfectNumber { // Pass in a value and solve at least how many perfect numbers public static int[] lessThan(int number) { int[] primes = Prime.findPrimes(number); ArrayList list = new ArrayList(); for(int i = 1; i <= number; i++) { int[] factors = factor(primes, i); if(i == fsum(factors)) list.add(new Integer(i)); } int[] p = new int[list.size()]; Object[] objs = list.toArray(); for(int i = 0; i < p.length; i++) { p[i] = ((Integer) objs[i]).intValue(); } return p; } // Decompose the factor private static int[] factor(int[] primes, int number) { int[] frecord = new int[number]; int k = 0; for(int i = 0; Math.pow(primes[i], 2) <= number;) { if(number % primes[i] == 0) { frecord[k] = primes[i]; k++; number /= primes[i]; } else i++; } frecord[k] = number; return frecord; } // Factor sum private static int fsum(int[] farr) { int i, r, s, q; i = 0; r = 1; s = 1; q = 1; while(i < farr.length) { do { r *= farr[i]; q += r; i++; } while(i < farr.length - 1 && farr[i-1] == farr[i]); s *= q; r = 1; q = 1; } return s / 2; } public static void main(String[] args) { int[] pn = PerfectNumber.lessThan(1000); for(int i = 0; i < pn.length; i++) { System.out.print(pn[i] + " "); } System.out.println(); } }Summarize
The above is all about the analysis of perfect number code in this article, I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out!