Trial division
prime number refers to a natural number that has no other factors except 1 and itself among natural numbers greater than 1. If a number z z If z is a non prime number, there is x × y = z x\times y = z x × y=z, let's set x ≤ y x\le y x ≤ y, then x ∈ [ 2 , z ] x \in [2, \sqrt{z}] x∈[2,z ]. Therefore, to verify whether a number is prime, just look at [ 2 , z ] [2, \sqrt{z}] [2,z ] whether there is a factor within the range.
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int number){
if(number<2)return false;
for(int i=2;i<=(int)sqrt(number);i++){
if(number%i==0)return false;
}
return true;
}
int main(){
int n;
cin >> n;
cout << is_prime(n) << endl;
return 0;
}
Sieve method
in [ 2 , n ] [2,n] It is a problem to be solved by the screening method to screen out the non prime numbers in the positive integer sequence of [2,n].
Eratosthenes sieve method
a number that is not a multiple of any prime number must be a prime number, which is the idea based on the Elsevier sieve method. Suppose there is { x ∣ 2 ≤ x ≤ n , x ∈ N } \{x|2\le x\le n,x\in N\} Positive integer sequence of {x ∣ 2 ≤ x ≤ n,x ∈ N} A A A. The algorithm of Elsevier sieve method is as follows:
- Fetch current sequence A i A_i Minimum decimal in Ai a i a_i ai( a i a_i ai (must be prime) and no longer put back the sequence.
- Remove current sequence A i A_i All in Ai a i a_i Multiple of ai ， to get the sequence A i + 1 A_{i+1} Ai+1.
- if A i + 1 A_{i+1} If Ai+1 ﹤ is empty, the algorithm ends, otherwise it will A i + 1 A_{i+1} Ai+1 ， returns to the first step as the current sequence.
the following is a brief proof a i a_i ai ， must be prime:
- When i = 1 i=1 i=1, yes a 1 = 2 a_1=2 a1 = 2 is a prime number.
- set up i = k i=k i=k and { a 1 , a 2 , ⋯ , a k } \{a_1,a_2, \cdots, a_k\} If {a1, a2,..., ak} are all prime numbers, then for the sequence A k + 1 A_{k+1} The smallest decimal in Ak+1 + a k + 1 a_{k+1} ak+1, yes { a 1 , a 2 , ⋯ , a k } \{a_1,a_2, \cdots, a_k\} {a1, a2,..., ak} is less than a k + 1 a_{k+1} All prime numbers of ak+1 + a k + 1 a_{k+1} ak+1 ， no { a 1 , a 2 , ⋯ , a k } \{a_1,a_2, \cdots, a_k\} The multiple of {a1, a2,..., ak}, so according to the theorem a k + 1 a_{k+1} ak+1 ， is a prime number.
- Therefore, according to mathematical induction a i a_i ai ， must be prime.
the code is as follows:
#include <iostream>
using namespace std;
void filter_prime(bool *const is_prime,size_t range){
is_prime[0] = is_prime[1] = false;
for(size_t i=2;i<=range;i++){///All numbers are assumed to be prime
is_prime[i] = true;
}
for(size_t i=2;i<=range;i++){///Find primes in range
if(is_prime[i]){
for(size_t j=2*i;j<=range;j+=i){///Mark all multiples of all primes as false
is_prime[j] = false;
}
}
}
}
int main(){
size_t n;
cin >> n;
bool *is_prime = new bool[n+10];
filter_prime(is_prime,n);
size_t c = 0;
for(size_t i=0;i<=n;i++){
c += is_prime[i];
}
cout << c << endl;
delete is_prime;
return 0;
}
Improved Elsevier sieve method
we can deduce a fatal disadvantage of the Eyre algorithm, that is, the repeated screening operation will be carried out for some numbers, for example, 6 will be screened out once by Prime 2 and again by 3. The improvement of the Ehrlich algorithm is to reduce repeated screening operations as much as possible. The main improvements are as follows:
- initialization
all even numbers except 2 are not prime numbers, so they are all filtered out during initialization. - Starting point of multiple
the starting point of the original multiple is 2, that is, the original screening operation is from prime numbers a a Starting at 2 times of a, i.e s = 2 a s=2 a s=2a, the improved method is to set the starting point as s = a 2 s= a^2 s=a2.
The following proves its rationality:
design ∀ k ∈ [ 2 , a ) ∈ N \forall k \in[2,a) \in N ∀k∈[2,a)∈N
there must be k = a ′ ⋅ b k=a^{'} \cdot b k=a ′⋅ b, where a ′ a^{'} a 'is prime b b b is an integer
rule k ⋅ a = a ′ ⋅ b ⋅ a = c ⋅ a ′ k \cdot a = a^{'} \cdot b \cdot a = c \cdot a^{'} k ⋅ a=a ′⋅ b ⋅ a=c ⋅ a ′, will b ⋅ a b \cdot a b ⋅ a is recorded as c c c
by a ′ < k < a a^{'}<k<a a′<k<a
get b ⋅ a = c > a ′ b \cdot a=c> a^{'} b⋅a=c>a′
rule k ⋅ a = c ⋅ a ′ k \cdot a = c \cdot a^{'} k ⋅ a=c ⋅ a 'and c > a ′ c> a^{'} c>a′， a > a ′ a> a^{'} a>a′
so [ 2 a , a 2 ) [2 a,a^2) [2a,a2) a a a multiples can be less than a a Prime number of a a ′ a^{'} A 'multiplied by a greater than a ′ a^{'} An integer of a '. That is, these numbers have been screened out by the smaller prime numbers, and there is no need to screen out.
the algorithm is screening [ 2 , n ] [2,n] For the non prime numbers in [2,n], after using this improved strategy, the screening work does not have to reach n n n, reaching n \sqrt{n} n It can be cut off when. because [ n , n ] [\sqrt{n},n] [n , n] is the starting point of the prime division operation s = a 2 s= a^2 s=a2 is greater than n n n. - Increment of multiple
the starting point of prime number screening operation is known s = a 2 s= a^2 s=a2, if the increment of the next screening operation multiple is an odd number, that is, screening in turn a 2 , ( a + 1 ) a , ( a + 3 ) a , ( a + 5 ) a , ⋯ , ( a + 2 k + 1 ) a a^2,(a+1)a,(a+3)a,(a+5)a,\cdots,(a+2k+1)a a2,(a+1)a,(a+3)a,(a+5)a,..., (a+2k+1)a is a repeated screening. Because a prime number must be odd and the sum of two odd numbers must be even, a prime number plus an odd number equals an even number, that is a + 2 k + 1 a+2k+1 a+2k+1 must be even. Because even times any integer is even, so ( a + 2 k + 1 ) a (a+2k+1)a (a+2k+1)a must be even. Because even numbers have been screened out during initialization, the screening operation is repeated. Therefore, the increment of screening operation multiple shall be even, i.e. screening in sequence a 2 , ( a + 2 ) a , ( a + 4 ) a , ( a + 6 ) a , ⋯ , ( a + 2 k ) a a^2,(a+2)a,(a+4)a,(a+6)a,\cdots,(a+2k)a a2,(a+2)a,(a+4)a,(a+6)a,⋯,(a+2k)a.
the code is as follows:
#include <iostream>
#include <cmath>
using namespace std;
void filter_prime(bool *const is_prime,size_t range){
is_prime[0] = is_prime[1] = false;
is_prime[2] = true;
for(size_t i=3;i<=range;i++){///Odd numbers greater than or equal to three are marked as true and even numbers are marked as false
is_prime[i] = true;
if(++i>range)break;
is_prime[i] = false;
}
for(size_t i=3;i<=sqrt(range);i+=2){
if(is_prime[i]){
for(size_t j=i*i;j<=range;j+=2*i){
is_prime[j] = false;
}
}
}
}
int main(){
size_t n;
cin >> n;
bool *is_prime = new bool[n+10];
filter_prime(is_prime,n);
size_t c = 0;
for(size_t i=0;i<=n;i++){
c += is_prime[i];
}
cout << c << endl;
delete is_prime;
return 0;
}
Linear sieve method (Eural sieve method)
#include <iostream>
#include <cmath>
using namespace std;
size_t filter_prime(bool *const is_prime,size_t range,size_t *const prime){
is_prime[0] = is_prime[1] = false;
for(size_t i=2;i<=range;i++){///All numbers are assumed to be prime
is_prime[i] = true;
}
size_t counter = 0;
for(size_t i=2;i<=range;i++){
if(is_prime[i]){
prime[counter++] = i;
}
for(size_t j=0;j<counter&&i*prime[j]<=range;j++){
is_prime[i*prime[j]] = false;
if(i%prime[j]==0)break;
}
}
return counter;
}
int main(){
size_t n;
cin >> n;
bool *is_prime = new bool[n+10];
size_t *prime = new size_t[n];
cout << filter_prime(is_prime,n,prime) << endl;
delete[] is_prime;
delete[] prime;
return 0;
}