java programming to achieve prime numbers and factorization code sharing

1. Solve for prime numbers

1.1 illustrates

First of all, let's look at the idea of what is prime? Prime numbers: a number that is divisible only by 1 and itself is called prime, and its counterpart is called a sum. And based on that notion, we can quickly come up with a way to do it, which is to start at 1 and keep trying to see if, from 1 to itself, any number is divisible by it.

So it turns out that prime numbers are pretty easy, but is there a more convenient way to do it? Here is a famous Eratosthenes method for finding prime numbers.

1.2 solution

First of all, we know that we can solve this problem by using loopback. If we divide a specified number by all numbers less than it, it will not be prime if it is divisible. However, how can we reduce the number of loopback checks? How do I find all primes less than N?

Let's say that the number that we're checking is N, then in fact we're just checking the square root of N, which is pretty simple, let's say that A*B=N, if A is greater than the square root of N, then in fact the number that we're checking before A is less than B is divisible into N. However, using the square root in the program will improve the accuracy, so you can use i*i < =N to check and perform faster.

Suppose there is a sieve to store 1 ~ N, for example:

23456789101112131415161718192021... N

Sieve the multiples of 2 first:

23579111315171921... N

Then sieve the multiples of 3:

235711131719... N

Sieve out the multiples of 5, sieve out the prime of 7, sieve out the multiples of 11... , so that all the numbers left are prime, which is Eratosthenes screening method (EratosthenesSieveMethod).

The number of checks can be further reduced. In fact, just check 6n+1 and 6n+5, that is, skip the multiples of 2 and 3, so that the number of checks for if 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 side 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. Factor

2.1 illustrates

So let's look at 1 first. What is factoring? When you take a number, and you convert it into the product of several other numbers, it's called factorization. Now, once you have this idea, if you look at the primes above, you should see that you're actually solving for a factor of a sum.

So factorization is basically using numbers that are less than the input number as a divisor, removing the input number as a divisor, and if it's divisible then it's a factor, and the faster way to do it is to find all prime numbers that are less than the input number, and see if it's divisible.

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, summarize

Solving prime numbers and factorization is the basic skill of learning programs and algorithms, so you should be proficient in it. The code here has only a few comments, which may be a little difficult for beginners, but it is the first step into the palace of program algorithms. You can copy this code to your own machine and step by step fill in the comments to make yourself more clear about the process.

Above is the Java programming to achieve prime numbers and factoring code to share all content, I hope to help you. Interested friends can continue to refer to other relevant topics in this site, if there is any deficiency, welcome to leave a message!