Method of finding prime number

Try division to judge prime numbers

Judge n Is it a prime number , It's enumeration [2,n-1] Can it be n Divisible . If there is , Then the return false, That means it's not a prime number ; Otherwise it's prime .

public static boolean isPrimeNum(int n){
    
    if (n <= 3) {
    
        return n > 1;
    }
    for(int i=2; i<Math.sqrt(n)+1; i++){
    
        if(n%i==0) return false;
    }
    return true;
}

If a number is not prime , So it must be the product of two numbers , And these two numbers are usually one big and one small , And the small one is less than or equal to the root n, Greater than or equal to the root n, We just need to enumerate that small range , See if it can be divisible , You can judge whether this number is possible .
for example ：100=250=425=520=1010 Just find 10 This interval is enough . There must be a corresponding one on the right. Don't worry about it .
The reason why this is less than the root n+1, It's the case where the root sign is to be included , for example 3*3=9. Include 3.

Please 666 A prime number

    public static void main(String[] args) {
    
        //  The fifth prime number is 11
        int count = 5;
        int i = 11;
        while (true){
    
            i += 2;
            if (isPrimeNum(i)){
    
                count++;
            }
            if(count == 666){
    
                break;
            }
        }
        System.out.println(i);

    }

    public static boolean isPrimeNum(int n){
    
        if (n <= 3) {
    
            return n > 1;
        }
        for(int i=2; i<Math.sqrt(n)+1; i++){
    
            if(n%i==0) return false;
        }
        return true;
    }

Find a prime number in a range

Generally speaking , Just use the above isPrimeNum Just judge . Like looking for 100 Inside , From 1 Judge one by one until 100...

for(int i=1; i<101; i++){
    
    if(isPrimeNum(i)){
    
        System.out.print(i+", ");
    }
}

After all, I already know 2 and 3 It's prime , Then judge directly 3 Then the odd number , Take two steps .

for(int i=1; i<101; i+=2){
    
    if(isPrimeNum(i)){
    
        System.out.print(i+", ");
    }
}

Elatosterni (Eratosthenes) Sieve method

Eratosthene method , Abbreviated as the ethmoid or the ethmoid , It's a simple algorithm for testing prime numbers proposed by Greek mathematician eratosthene . To get a natural number n All prime numbers within , Must put no more than the root n The multiple elimination of all prime numbers , All that's left is the prime number .

Delete type

The original algorithm is as follows ：（n take 25）

1. List from 2 To 25 All the sequences of ：
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. Mark the first prime in the sequence , That is to say 2, The sequence becomes ：
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. Put... In the sequence ,2 Cross out the multiples of , The sequence becomes ：
   2 3 5 7 9 11 13 15 17 19 21 23 25
4. If in this sequence The maximum number Less than The last marked prime The square of , So all the numbers in the rest of the sequence are primes , Or go back to step two .
5. In this case , because 25 Greater than 2 The square of , We return to the second step ：
6. The first prime in the rest of the sequence is 3, In the main sequence 3 Cross out the multiples of , The main sequence becomes ：
   2 3 5 7 11 13 17 19 23 25
7. The primes we get are ：2,3
8. 25 Still greater than 3 The square of , So we have to return to the second step ：
9. The first prime in the rest of the sequence is 5, Also, in the sequence 5 Cross out the multiples of , The main sequence becomes ：
   2 3 5 7 11 13 17 19 23
10. The primes we get are ：2,3,5
11. because 23 Less than 5 The square of , Out of the loop .
12. Conclusion ：2 To 25 The prime in between is ：2 3 5 7 11 13 17 19 23.

# Python
def isPrimeNum(x):
    if x <= 3:
        return x>1
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True

def Eratosthenes(n):
    arr = [i for i in range(2,n+1)]
    arr_c = arr.copy()
    prime = []
    while True:
        firstNum = arr[0]
        if isPrimeNum(firstNum):
            prime.append(firstNum)	#  Add this prime number to the array of pure prime numbers 
            arr.remove(firstNum)	#  Delete this prime number and its multiples 
            #  The subscript value is smaller than the specific value 2. such as arr[0] yes 2,arr[14] yes 16
            for j in range(firstNum*firstNum-2, len(arr_c), firstNum):
                #  such as 6 The number of , Prime number is 2 Deleted once when . Prime number is 3 If you delete it again, you will report an error 
                #  Add one count Method , Only when there is this number can it be deleted , But this method affects efficiency 
                if arr.count(arr_c[j]) != 0:
                    arr.remove(arr_c[j])
            if firstNum ** 2 > arr[-1]:
                break
        else:
            arr.remove(firstNum)
    prime = prime + arr
    return prime

if __name__=='__main__':
    a = Eratosthenes(100)
    print(a)

Two arrays are created in the code . The contents of the two arrays are the same , All stored from 1 To n Of N Consecutive values . Because deletion will cause dynamic changes to the array , The subscript of the array is not very good . For example, deleting 2 A multiple of the , take arr[47] The value should be 48, But because the array has changed ,arr[47] It could be 77, Or subscript 47 It is directly considered to be beyond the boundary ...

#  In this way, there is no need to worry about the change of subscript 
def Eratosthenes(n):
    arr = [i for i in range(1,n+1)]
    prime = []
    while True:
        firstNum = arr[0]
        if isPrimeNum(firstNum):
            num.append(firstNum)
            for j in arr:
                if j%firstNum==0:
                    arr.remove(j)
            if firstNum ** 2 > arr[-1]:
                break
        else:
            arr.remove(firstNum)
    prime = prime + arr
    return prime

Marker type 1

This is my first way of writing , After writing, I found that it was different from what I found . The algorithms in the code are listed in detail as follows ：（ Like this n yes 25）

1. List from 1 To 24 All the sequences of ：
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. Find the first number , That is to say 1,1 Not prime , Make a mark . Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. Find the second number , That is to say 2,2 Prime number , take 2 All multiples of are marked .2 The square of is not greater than 25. Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. Find the third number , That is to say 3,3 Prime number , take 3 All multiples of are marked .3 The square of is not greater than 25. Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24 25
5. Find the fourth number , That is to say 4,4 Not prime , Make a mark . Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24 25
6. Find the fifth number , That is to say 5,5 Prime number , take 5 All multiples of are marked .5 The square of is not greater than 25. Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425
7. Find the sixth number , That is to say 6,6 Not prime , Make a mark . Subscript plus 1. The cycle continues ,,,
   1 2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425
8. Find the seventh number , That is to say 7,7 Prime number , take 7 Double speed is marked .7 The square of is greater than 25. The loop ends ...
   2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425
9. Conclusion ：2 To 25 The prime in between is ： 2 3 5 7 11 13 17 19 23

The drawback of markup is that there are many repeated calculations .
such as 18, Choose to 2 When it's prime , It was marked once , alike ,3 When it is a prime number, it is marked again . So the more factors , The more times they are marked . Although I did the square processing when initializing the subscript , But it doesn't work very much .
And in the code , I always compare the square of the current prime number with the last number in the array , It doesn't pay attention to whether the last number in the array is marked . This is also a point to be optimized .

package com.company;
import java.util.ArrayList;
import java.util.List;
public class test {
    
    public static void main(String args[]){
    
        System.out.println(Eratosthenes(100));
    }
    public static List<Integer>  Eratosthenes(int n) {
     // Parameters n Representative range 
        //  Create tag array , The initial values are all 0. Marked as -1 All of them are not prime numbers 
        int[] is_prime = new int[n];
        for (int num = 1; num <= n; num++) {
    
            if (isPrimeNum(num)){
    
                //  if num Prime number , Mark all its multiples as -1
                //  The marked number is larger than its index 1
                //  Subscript starts with square , It can reduce the repeated marking of some numbers 
                //  such as num=5, To mark 5 Multiple . It can be directly from the number 25 Start . because 10 and 20 By num=2 Marked ,15 By num=3 Marked 
                for(int j=num*num-1; j < n; j=j+num){
    
                    is_prime[j] = -1;
                }
                if (num * num > n) break;
            }else {
    
                is_prime[num-1] = -1;
            }
        }
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++){
    
            if (is_prime[i] == 0) list.add(i+1);
        }
        return list;
    }
    public static boolean isPrimeNum(int n){
    
        if (n <= 3) return n > 1;
        for(int i=2; i<Math.sqrt(n)+1; i++){
    
            if(n%i==0) return false;
        }
        return true;
    }
}

Marker type 2

The algorithms in the code are listed in detail as follows , use C/C++ It belongs to this ：（ Like this n yes 25）

1. List from 2 To 25 All the sequences of ：
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. Find the first number , That is to say 2,2 Not marked . It's a prime number . hold 2 Put in an array prime in . And put 2 All multiples of are marked ,,,
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. Find the second number , That is to say 3,3 Not marked . It's a prime number . hold 3 Put in an array prime in . And put 3 All multiples of are marked ,,,
   2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24 25
4. Find the third number , That is to say 4,4 Have been marked , hold 4 All multiples of are marked ,,,（ The points to be optimized come out ）
   2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24 25
5. Find the fourth number , That is to say 5,5 Not marked . It's a prime number . hold 5 Put in an array prime in . And put 5 All multiples of are marked ,,,
   2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425
6. Find the fifth number , That is to say 6,6 Have been marked . hold 6 All multiples of are marked ,,,
   2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425
7. Cycle all the time n-1 round

The advantage of this algorithm is that it does not need to judge whether the number is a prime number , Just see if it has been marked . The disadvantage is the outermost for The cycle goes to the end
The array used to store the tag condition in the code isprime. The first element is ignored directly , So we add 1. The advantage is that the number and its subscript are not misplaced . such as 4 yes 2 Multiple , Directly assign values isprime[4]=true .

public static void main(String[] args) {
    
	int n = 50;                     //  Range 
    int[] prime = new int[n];       //  Record the number prime
    int index = 0;                  //  Mark prime The subscript 
    boolean[] isprime = new boolean [n+1];//  Judge whether it has been marked , The initial value is zero false. Add 1 To make subscripts correspond to numbers , It's not like the top is misplaced 
    for(int i=2; i<=n; i++)
    {
    
        if(!isprime[i])
        {
    
            prime[index] = i;
            index++;
        }
        for(int j=i+i; j<=n; j=j+i) // All his multiples are marked 
        {
    
            isprime[j]=true;
        }
    }
    for(int i: prime){
    
        System.out.print(i+", ");
    }
    //  The output looks like this ... It's all in the back 0
    // 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 0, 0, 0, 0, 0, 0, 0, 0, 
}

Here is my improved algorithm
isPrime An array is a sieve , Or a tool . Just make this tool , Then the array storing prime numbers does not need to be created

public static void main(String args[]){
    
    int n = 50;                          // Prime range 
    int[] isPrime = new int[n+1]; // Judge whether it has been marked , The initial value is zero 0, Marks that are not prime numbers are -1
    for(int i=2; i<=n; i++)
    {
    
        if(isPrime[i]==0)
        {
    
            if(i*i＞n){
    
                 break;
            }
            for(int j=i*i; j<=n; j=j+i) // All its multiples are marked 
            {
    
                isPrime[j]=-1;
            }
        }
    }
    
    for (int i = 2; i < isPrime.length; i++) {
    
        if (isPrime[i]==0) System.out.print(i+", ");
    }
}

Euler screen

Marking method in Ehrlich sieve , Duplicate calculations .
The Euler sieve is improved on the basis of Ehrlich sieve , It effectively avoids this double calculation .
What kind of thinking is it ？ That is, the sieve encounters a prime number and calculates its multiple to the end , And the Euler sieve only uses it multiply Known prime numbers The product of , If prime numbers can be divisible, stop marking back .

public static void main(String[] args) {
    
    int n = 25;
    int[] prime = new int[n];
    int index = 0;
    boolean[] isprime = new boolean[n+1];
    for (int i = 2; i <= n; i++) {
    
        if (!isprime[i]) {
    
            prime[index] = i;
            index++;
        }
        for (int j = 0; j < index && i * prime[j] <= n; j++){
    // Enumeration in the range of known primes 
            isprime[i * prime[j]] = true;//  Mark product 
            if (i % prime[j] == 0)
                break;
        }
    }
    for(int i: prime){
    
        System.out.print(i+", ");
    }
}

i=5, Marked are 10,15
i=6, Only 12
Euler's idea is to be closer to me and I'll mark it , such as i=6 when , Mark only 12 Instead of marking 18,18 Leave to i=9 When it's time to mark . The time complexity of Euler sieve is O(n), Because each number is marked only once .
You may ask why if (i % prime[j] == 0) Will be break.
If i%prime[j]==0, Then it means i=prime[j]*k,k It's an integer .
So if we go to the next round
i*prime[j+1]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1]). When i=k*prime[j+1] The two positions are in conflict and double counting , So once you meet something that can be divisible, stop .