Less than 100 secrets about prime numbers

Preface ：

Delayed for a day , It feels too Nice 了 . So I wrote this blog with difficulty when I almost planned to break the watch .
Because the author becomes lazy , I didn't study hard today , So there's no Euler sieve board , There is no board for prime test , There is no board with large number decomposition . But I try to mention them all . Find your own board , Or write it later and then add .
If the author encounters an unexpected change , Readers don't know what to learn , Please play the game carefully , Enjoy life .
 
 

The test of prime numbers ：

First, let's talk about what prime numbers are
Now let's introduce how to test prime numbers , According to the author's learning order .
 
First , The first people to know should be simple $o(\sqrt{n})$ Trial division of .（ This is not hard to , Let's not talk about the principle ）

bool isPrime(ll n)
{
    
    if(n==1)return false;
    for(ll i=2;i*i<=n;i++)if(n%i==0)return false;
    return true;
}

 
later , Namely $o(nlogn)$ Ehrlich sieve method , It's OK after screening $o(1)$ test .（ It's not hard , Let's not talk about the principle ）

notPrime[1]=1;
for(ll i=1;i<=n;i++)if(!notPrime[i])
{
    
    for(ll j=2*i;j<=n;j+=i)notPrime[j]=1;
}

This screening method also has Another use , For example, judgment $[a,b]$ The prime number in , among $1<a<b<1e9$ And $b-a<1e5$. here , We can sift out $\sqrt{b}$ All prime numbers in the range , Then take these prime numbers and sift this interval , You can get the answer .

 
later , Namely $o(n)$ The Eulerian sieve , After screening, you can $o(1)$ test .

 Ashamed to speak , The author can't tear the Euler sieve by hand , Plus I didn't study hard today .
 Due to strong copyright awareness , The author didn't go anywhere else to pull the board and put it here .
 When the area function is sieved, fill in .
 This is a hidden poem .

 
 
And finally $MillerRabin$ Prime test of , stay long long It's also very useful in the range . This is a random algorithm , Carry out multiple inspections , The probability of each test being correct is about $\frac{1}{4}$, The more inspection times, the more accurate , The complexity is $o(t\times logn)$, among $t$ Is the number of inspections .
But after all, it's a random algorithm , With enough complexity , Single inspection still considers $o(\sqrt{n})$ Your trial division is better .

Let's talk a little about the principle .
Let's start with the simple Fermat prime test .
according to Fermat's small Theorem ： When $p$ As a prime number , And $gcd(a,p)=1$ when ,$a^{p-1}\equiv 1(modp)$.
that , If we want to judge the number $p$ Don't meet this condition , Then it must not be prime .
But just based on this, there are big loopholes , Because Fermat's theorem is not a necessary and sufficient condition , Sufficiency holds , But the necessity is not tenable .
Some numbers satisfy sufficient conditions , Without meeting the necessary conditions , This is it. Fermat pseudo prime number .
Because of their existence , This makes this test method a big problem .
 
But the Fermat prime test can score most of the scores . Then we need to find another detection method to further judge .
So we use Second detection ： if $p$ As a prime number , Then the equation $x^2\equiv 1(modp)$ The solution of is $x=1$ or $x=p-1$.
 
So how to use it , The key part is coming , Let's start by listing a few things we need to do .

• We want a random number $a$.
• Use $a$ Fermat test , have a look $a^{p-1}\equiv 1(modp)$ Is it true .
• Then we have to make a second detection , But solving the equation is troublesome , But now we have $a^{p-1}\equiv 1(modp)$, So we just need to see $a^{\frac{p-1}{2}}$ Is it $1$ or $p-1$ Just fine .

Come here , We found out , Take the Fermat prime test quickly , And the fast power uses $a^{\frac{p-1}{2}}$ Such things .
Then you can write it together .
And when the $a^{\frac{p-1}{2}}$ yes $1$ when , You can use him for a second detection ; On the contrary, if it is $p-1$ Can't continue to use .
So the subcode can be written .

 My country and I   A moment cannot be divided 
 Wherever I go   A song of praise came out 
 I sing about every mountain   I sing about every river 
 Smoke from the   Little village   There is a rut in the road 
 My dear motherland   I will always cling to your heart 
 You tell me with your mother's warmth 
 My country and I   Like a sea and a spray 
 Waves are the sons of the sea   The sea is the support of that wave 
 Whenever the sea smiles   I am the vortex of laughter 
 I share the sorrow of the sea   Share the joy of the sea 
 My dear motherland   You are the sea that never dries up 
 Always give me   Clear waves   The song in my heart 
 La …… La ……
 Always give me   Clear waves   The song in my heart 

that , The test method of prime number is introduced .
 
 

Factorization ：

First , It's tradition $o(\sqrt{n})$ Decomposition of , I don't think I can write anymore .
 
Then the same as the prime test Strange sex skill , Large number decomposition .
Complexity can achieve $o(n^{0.25})$, But like the prime test, it's a random algorithm , So it's not very stable , Unless you have to , Otherwise, use less . I haven't seen the principle yet , Don't write .
The code is as follows ：

 As for the code , As you can see now , There is no such thing , But there are still a lot of online boards .

Prime density ：

Also known as the prime distribution theorem . That is to say , Two adjacent prime numbers are not too far apart , Is probably $o(lo{g}^{2}n)$ Grade .$1e9$ The maximum spacing in the range is $300$ Small （ Or perhaps $250$？）.($1e18$ It doesn't seem to exceed $500$？)
Specific applications can be seen many times , For example, let you ask less than $n(2<n<1e9)$ The maximum prime number of , With this theorem , You can judge .