π Author: Linux ape
π Introduction: CSDN blog expert ποΌ Huawei cloud sharing expert ποΌ Linux, C/C + +, cloud computing, Internet of things, interview, question brushing and algorithm. Please consult me, pay attention to me and chat privately if you have any questions!
π Attention column: attention π₯ University algorithm into God π₯ The column is not lost, and the high-quality good articles are constantly updated π
catalogue
π© 2.3} linear sieve method for prime
In the process of algorithm learning, the prime problem has always been a hot spot, and there are many problems about prime. This article will explain prime numbers and how to solve prime numbers.
ββ
Brother ape has been sharing knowledge with the attitude of knowing what is and why. Let's take a look at the definition of prime.
π 1, What is prime
Prime number refers to the number that cannot be divided by other natural numbers except 1 and itself, that is, there are only two positive factors of 1 and itself, which is also called prime number.
For example, prime numbers within 10 include {2,3,5,7}, which can only be divided by 1 and itself.
Now that you know what a prime number is, let's judge whether a number is a prime number.
// Prime numbers within 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
πΆπΆπΆ I am a gorgeous dividing line πΆπΆπΆ
π 2, Judgement prime
There are many methods to judge prime numbers. Here are three common methods. One is to judge whether a number is a prime number according to the definition, the other is the square method, and the other is the linear sieve method.
π© 2.1 definition method
Suppose to judge whether n is a prime number, the definition method is to judge whether n can be divided from 2 to n-1 in turn. If there are divisible numbers, then n is a composite number, otherwise it is a prime number. Is it the same as the definition!
The code is shown below.
bool isPrime(int n) {
if(n <= 3) // Simplify operation
return true;
for(int i = 2; i < n; ++i) {
if(n % i == 0) // Determine whether i can divide n
return false;
}
return true;
}π© 2.2 opening method
If n is a composite number, there must be a pair of factors q1 and q2, and the conditions q1 < = sqrt (n), q2 > = sqrt (n), q1 * q2 = n are satisfied. Then, it only needs to find q1 to prove that it is a composite number, so the judgment range is reduced to 2 ~ sqrt(n).
For example, find out whether 10 is a prime number. The factors of 10 are 2 and 5. Find out whether the integer of 2 ~ sqrt(10) can be divided by 10, because 2 is within this range.
The code is shown below.
bool isPrime(int n) {
if(n <= 3) // Simplify operation and deal with special situations 2
return true;
for(int i = 2; i <= sqrt(n); ++i) { // sqrt is the square function
if(n % i == 0)
return false;
}
return true;
}π© 2.3} linear sieve method for prime
Principle of linear screening method: each composite number is screened only once by the minimum prime factor.
The linear screening method screens out the composite number through the minimum quality factor of each composite number. Each composite number is screened only once, because a composite number can be decomposed into the product of a prime number and another number. When marking the composite number, it is marked with the prime factor with the smallest composite number.
For example, mark 30 is marked with 2 * 15 instead of 3 * 10.
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX_LEN = 1000;
int num = 0;
int prime[MAX_LEN];
bool isPrime[MAX_LEN];
/*
* Linear sieve method,
*/
bool judgePrime(int n) {
memset(isPrime, false, sizeof(isPrime));
for(int i = 2; i <= n; ++i) {
if(!isPrime[i])
prime[num++] = i ;
for(int j = 0; (j < num && i * prime[j] <= n); ++j) {
isPrime[i * prime[j]] = true ;
if(!(i%prime[j]))
break ;
}
}
}
int main()
{
judgePrime(100);
for(int i = 0; i < num; ++i) {
cout<<prime[i]<<" ";
}
cout<<endl;
return 0;
}In the above three methods, method 1 is generally not used because its complexity is O(n). Method 2 is usually used to determine whether a single number is a prime number. Method 3 is usually used to screen out primes in an interval.
πΆπΆπΆ I am a gorgeous dividing line πΆπΆπΆ
π 3, Actual combat drill
After mastering the above methods, hurry to practice!
[1] http://poj.org/problem?id=2262
πΆπΆπΆ I am a gorgeous dividing line πΆπΆπΆ
π 4, Summary
This paper mainly explains the solution methods of prime numbers, mainly mastering the solution methods of single prime numbers and interval prime numbers, which can be further understood according to the two topics in the actual combat drill.
π It's not easy to tidy up. I feel it's helpful. Remember the support of "one key three links"! If you have questions, you can leave a message in the comment area π¬οΌ Thank you for your support! π€ Brother ape will continue to output "high-quality articles" to feed back to you! π€πΉπΉπΉπΉπΉπΉπ€