Number theory -- simple sieve method, Ehrlich sieve method and linear sieve method

number theory

Combination count

Gauss elimination

Simple game theory

Definition of prime number 、 Determination of prime numbers

Definition and judgement of prime number 、 Decomposing prime factor

The second game of the 12th Blue Bridge Cup C++B Set real questions _ Xiaoxuecai's blog -CSDN Blog

Sieve prime number

First write all the numbers in the prime table , Look back from the past , Sift out all multiples of each number , After screening , All the remaining numbers are prime numbers

For any number P for , If it hasn't been deleted , It means from 2 ~ P - 1 None of the numbers in the list put P Sift out , explain P No 2 ~ P - 1 A multiple of any number in , explain 2 ~ P - 1 There is not one of them P The divisor of , therefore P It's a prime number

 

Time complexity analysis ：

When i be equal to 2 Time to cycle n / 2 Time , When i be equal to 3 When , Circulated n / 3 Time

Harmonic series

C It's the Euler constant , about 0.57721566490153286060651209

It is deduced that the time complexity of the naive sieve method is O( nlogn )

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1000010;

int primes[N],cnt;
bool st[N];

void get_primes(int n) 
{
	// from  2  To  n  enumeration 
    for(int i = 2;i <= n;i++ )
    {
        // If the current number has not been filtered   It is a prime number 
        if(!st[i]) 
        {
            primes[cnt ++ ] = i;
        }
        // Sift out all multiples of each number 
        for(int j = i + i;j <= n;j += i) st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

Ethmoidal method

We can optimize the simple sieve method , You can find , It is not necessary to delete all multiples of each number , You can delete multiples of all prime numbers

Screen according to the previous screen method , If you stay P, Just explain P It's a prime number , We can find out , In fact, there is no need to 2 ~ P - 1 Enumerate them all , Only need to 2 ~ P -1 It is OK to judge the prime number in

Just promise 2 ~ P - 1 The multiples of all prime numbers in are not P( P It's a prime number ) The divisor of ,P It's a prime factor , At the time of screening , Just sift out all multiples of prime numbers , When a number is not a prime number , You don't have to sift out all its multiples

Time complexity analysis ： Now just calculate 1 ~ 1 / n Harmonic series of all prime numbers , Theorem of prime numbers ：1 ~ n There is n / logn A prime number

It was supposed to be n Number , Now just calculate n / logn Number , The time complexity is O( nloglogn ) and O(n) It is basically a level

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1000010;

// primes[] Store all primes 
int primes[N],cnt;
// st[x] Storage x Whether it has been screened out 
bool st[N];

void get_primes(int n) 
{
	// from  2  To  n  enumeration 
    for(int i = 2;i <= n;i++ )
    {
        // If the current number has not been filtered   It is a prime number 
        if (st[i]) continue;
        primes[cnt++] = i;
        // Put the loop in the judgment condition 
        // Sift out all multiples of each prime number 
        for(int j = i + i;j <= n;j += i) st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

Ehrlich sieving is faster than simple sieving 3 About times

Linear sieve method

Try to sift out each composite number with one of its prime factors

The data range is 10^7 The linear sieve method is about twice as fast as the Ehrlich sieve method

The time complexity is linear

Prime sieve ( Linear sieve method )_Wansit The blog of -CSDN Blog _ Linear prime sieve

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1000010;

int primes[N],cnt;
bool st[N];

void get_primes(int n) 
{
	// from  2  To  n  enumeration 
    for(int i = 2;i <= n;i++ )
    {
        // If it is a prime number, add it to the prime number table 
        if(!st[i]) primes[cnt++] = i;
        // Enumerate all prime numbers from small to large   When the prime number is greater than  n / i break
        for(int j = 0;primes[j] <= n / i;j++ ) 
        {
            // Sift out primes[j] * i  No matter what  primes[j]  It must be  primes[j] * i  The minimum quality factor of 
            // It must be the least prime factor of this number to filter this number 
            st[primes[j] * i] = true;
            //primes[j] It must be i The minimum quality factor of  primes[j] Are all prime numbers enumerated from small to large 
            if(i % primes[j] == 0) break; 
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

n = 10^6 Within the scope of , The running time of linear sieve method is 45 ms It is similar to the Ehrlich sieve method

n = 10^7 Within the scope of , Linear sieve method is about twice as fast as Ehrlich sieve method

Linear sieve method

Ethmoidal method

Next, let's see why the linear sieve method is linear ？ What is the principle ？

n Will only be sifted out by its minimum quality factor

j When filtering, you enumerate all prime numbers from small to large , Sum the current prime number with each time i The product of is sifted out

Linear sieve analysis _ Ms. Shi's blog -CSDN Blog _ Linear sieve method

Any composite number must be sifted out , Any number x There must be and only one minimum prime factor , So each number is filtered only once , So it's linear

final if There are two cases of statements ：

（1） if i % primes[ j ] == 0 , shows primes[ j ] yes i The minimum quality factor of , that primes[ j ] It must be primes[ j ] * i The minimum quality factor of . for example ：4 % 2 == 0 ,2 yes 4 The minimum quality factor of , And 2 It's also 2 * 4 The minimum quality factor of .

（2） if i % primes[ j ] != 0 , Because we enumerate all prime numbers from small to large , And we didn't enumerate i Any prime factor of , Now primes[ j ] Must be less than i All the qualitative factors of , however primes[ j ] It must be primes[ j ] * i The minimum quality factor of .

for example ：9 % 2 ！= 0,2 Must be less than 9 The minimum quality factor of , but 2 It must be 2 * 9 The minimum quality factor of .（ 9 The minimum quality factor of is 3,9 To enumerate to 3 only break, but 9 * 2 The minimum quality factor of is 2, When enumeration to 2 You can break ）