1. Solve the prime number
1.1 Description
First of all, let’s understand the concept, which is what is prime numbers? Prime number: If a number can only be divisible by 1 and itself, such a number is called a prime number, and the corresponding number is called a sum number. Based on this concept, we can quickly think of a method, which is to start from 1 and constantly test to see if there are numbers that can be divided by them from 1 to itself.
From this point of view, it is actually very simple to find prime numbers. Is there a more convenient way for us? Here is a famous method of finding prime numbers by Eratosthenes.
1.2 Solution
First of all, you can use circles to solve this problem. Divide a specified number by all numbers smaller than it. If you can divisive it, it is not a prime number. However, how to reduce the number of circles checks? How to find all prime numbers smaller than N?
Assuming that the number to be checked is N, in fact, just check the root number of N. The reason is very simple. Assume that A*B=N, if A is greater than N's root number, in fact, check before being less than A can first check that the number B can be divisible. However, using the root number in the program will have the problem of accuracy, so you can use i*i<=N for checking and the execution will be faster.
Let's assume that there is a sieve to store 1~N, for example:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ......... N
First sift the multiples of 2:
2 3 5 7 9 11 13 15 17 19 21 ......... N
Then sift the multiples of 3:
2 3 5 7 11 13 17 19 ......... N
Then sieve the multiples of 5, then sieve the prime number of 7, then sieve the multiples of 11..., in this way, the numbers left at the end are all prime numbers, this is the Eratosthenes screening method (EratosthenesSieveMethod).
The number of checks can be reduced. In fact, just check 6n+1 and 6n+5, that is, skip the multiples of 2 and 3 directly, so that the if checking action in the program can be reduced.
1.3 Code
import java.util.*; public class Prime { public static int[] findPrimes(final int max) { int[] prime = new int[max+1]; ArrayList list = new ArrayList(); for(int i = 2; i <= max; i++) prime[i] = 1; for(int i = 2; i*i <= max; i++) { // This can be improved if(prime[i] == 1) { for(int j = 2*i; j <= max; j++) { if(j % i == 0) prime[j] = 0; } } } for(int i = 2; i < max; i++) { if(prime[i] == 1) { 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; } public static void main(String[] args) { int[] prime = Prime.findPrimes(1000); for(int i = 0; i < prime.length; i++) { System.out.print(prime[i] + " "); } System.out.println(); } }2. Factorization
2.1 Description
As shown above, let’s first understand what factorization is? Converting a number into the product of several other numbers is called factorization. After understanding this concept, we should be able to understand that we are solving a factor of a sum number compared with the above solution to solve the prime number.
Factorization basically uses the value smaller than the input number as a divisor, and removes it with the input number. If it can be divided, it will be regarded as a factor. The faster solution is to find all prime numbers smaller than the number and try to see if it can be divided.
2.2 Code
import java.util.ArrayList; public class Factor { public static int[] factor(int num) { int[] pNum = Prime.findPrimes(num); ArrayList list = new ArrayList(); for(int i = 0; pNum[i] * pNum[i] <= num;) { if(num % pNum[i] == 0) { list.add(new Integer(pNum[i])); num /= pNum[i]; } else i++; } list.add(new Integer(num)); int[] f = new int[list.size()]; Object[] objs = list.toArray(); for(int i = 0; i < f.length; i++) { f[i] = ((Integer) objs[i]).intValue(); } return f; } public static void main(String[] args) { int[] f = Factor.factor(100); for(int i = 0; i < f.length; i++) { System.out.print(f[i] + " "); } System.out.println(); } }3. Summary
Solving prime numbers and factorization is the basic skill of learning programs and algorithms, and you should master them proficiently. The code here only has a small number of comments, which may be a bit difficult for beginners, but this is the first step to entering the palace of program algorithms. You can copy this code to your machine and fill in the comments step by step to make your program process clearer.
The above is all the content of this article about Java programming implementation to achieve prime numbers and factorization code, and 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!