Java programming for prime number and factorization code sharing

1. Solving prime numbers

1.1 description

First of all, let's understand the concept of what is called prime number? Prime number: if a number can only be divided by 1 and itself, such a number is called prime number, and the corresponding number is called sum number. Based on such a concept, we can quickly think of a method, that is, starting from 1, constantly test to see whether any number from 1 to itself can be divided by him.

In this way, it is actually very simple to find prime numbers. Do we have a more convenient way? This paper introduces a famous method of Eratosthenes for finding prime numbers.

1.2 solution

First of all, we know that this problem can be solved by loop. Divide a specified number by all numbers less than it. If it can be divided, it is not a prime number. However, how to reduce the number of loop checks? How to find all prime numbers less than n?

If the number to be checked is n, in fact, it is OK to check to the open root of N. The reason is very simple. Suppose a * b = n. if a is greater than the open root of N, in fact, B can be checked before it is less than A. this number can be divided by n. However, the use of open radical in the program will affect the accuracy, so I * I < = n can be used for inspection, and the execution is faster.

Let's assume that there is a sieve storing 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

Sift out the multiple of 2 First:

2　3　5　7　9　11　13　15　17　19　21 ........ N

Sieve out the multiples of 3:

2　3　5　7　11　13　17　19　........ N

Sift out multiples of 5, prime numbers of 7, multiples of 11, In this way, all the numbers left in the end are prime numbers, which is the Eratosthenes sievmethod.

The number of checks can be further reduced. In fact, just check 6N + 1 and 6N + 5, that is, directly skip the multiples of 2 and 3, so that the check action of if in the program can be reduced.

1.3 code

2. Factorization

2.1 description

As shown above, let's first understand what is factorization? Converting a number into the product of several other numbers is called factorization. When we understand such a concept, we should be able to understand that we are actually solving a factor of sum number by comparing the above solution of prime number.

Factorization basically uses the value less than the input number as the divisor and removes the input value. If it can be divided, it will be regarded as a factor. The faster solution is to find all prime numbers less than the number and try whether it can be divided.

2.2 code

3. Summary

Solving prime numbers and factorization is the basic skill of learning programs and algorithms. You should master them skillfully. There are only a few comments in the code here. It may be a little difficult for beginners, but this is the first step into the palace of program algorithms. You can copy this code to your own machine and gradually fill in the comments to make your program flow clearer.

The above is all about the sharing of prime number and factorization code in Java programming. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message and point out!