The C++ implementation takes the instance of the largest prime number less than n

2020-05-19 05:22:26
OfStack

Enumeration is a problem solving strategy based on the guessing of the existing knowledge mirror answer

Problem: find the largest prime number less than n

Analysis:

There is no mathematical formula that allows this prime number to be calculated according to N

We thought:

Is N-1 a prime number? Is N-2 a prime number? .
Therefore, we judge whether N-K is a prime number:
N-K is a sufficient and necessary condition for prime Numbers: N-K is not divisible by any one of [2, n-k]
The problem of determining whether N-K is a prime number can be converted to:
Find all prime Numbers less than N-K (find the largest prime number less than N if "n is not divisible by any prime number in [2,n]", instead of an integer)
The number 1 that is not divisible by any prime in [2,n] must be prime because the integers are all divisible by prime,
So there's no need to check all integers, just ok for all primes

Solutions:

2 is a prime number, PRIM 0

According to PRIM 0, PRIM 1... PRIM K, looking for the smallest prime number larger than PRIM K PRIM K+1

If PRIM K+1 is greater than N, then PRIM K is the prime we need to find, otherwise keep looking

Enumeration:

List the elements from a possible set of 11
Give a guess based on what you know
For example, if 2 is a prime number, is 2 the solution to this problem

Enumeration algorithm:

For each item in the set of possible solutions to the problem:
Determine which is true according to the test conditions given to the problem
The solution to the problem is what makes the condition true

Enumeration process:

Judge if the guesses are correct
Is 2 the largest prime number less than N?
Make a new guess:

There are two key factors to note:

1. The result of the guess must be something that did not appear in the previous guess. Each time you guess the prime number 1, it must be larger than the prime number you found
2. Eliminate wrong answers early in the guessing process. For example, apart from 2, only an odd number can be prime

Questions to be considered in the enumeration process:

1. Give the solution space and establish a brief mathematical model
What are the possible scenarios?
The number of variables in the model is as small as possible, and they are independent of each other
Find the condition in "the largest prime number less than N" : "n is not divisible by any prime number in [2,n]"
Instead of "n is not divisible by any integer in [2,n]"

2. Reduce your search space

Knowledge is used to reduce the value range of variables in the model to avoid unnecessary calculation
For example, fewer times the loop body is executed in the code
Except for 2, only an odd number can be prime, {2,2*i+1, |, 1 < =i,2*i+1 < n}

3. Use the right search order

The traversal order of the search space corresponds to the conditional expression 1 in the model
For example: pair {2,2*i+1, |, 1 < =i,2*i+1 < n}, in the order from small to large

Enumeration key (enumeration core) :

Reduce the size

Example code:


#include <iostream>
using namespace std;
int prim[50000];// To store all primes  
int primNum=0;// Used to record  prim The number of primes already stored in an array  
int times=0; // Used to record the total number of judgments for solving the problem  
int primLessN(int n);
int primLessN_2(int n);
bool isPrimMothed(int n); // judge 1 Whether the number is prime or not  

/*
   methods 1 : enumeration method judged by the head and back primes: 
   For a "less than N The condition in "is" n Can't be [2,n) In any 1 All primes are divisible ", not whole Numbers 
   
   when n=10 0000 When, 
  ans=99991
  times=4626 4478 time  
  primNum=9592 
  
   Every time I 1 Each of the prime Numbers is judged and traversed 1 Let's look at the previous prime table 
   The judge 10 0000 The outer loop goes away 50000 The layer of each, 1 The prime Numbers are zero 1 The traversal of a prime table before the second 
  50000* ( 1+2+3+...+9592)=50000* 4600 8082
   No, no, no 50000 Minus the non-prime Numbers  
   from  50000* 4600 8082 As you can see, it's mainly the time that it took for the primes before, and it's almost no time for the non-primes 
   A prime number = 4626 4478-4600 8082= 25 6450 
   only 25 Wan, although it's still a lot more than the bottom, because it's from the front to the back  
*/
int primLessN(int n)
{
  prim[0]=2; //2 Is the smallest prime number 
  primNum++; 
  for(int i=3;i<n;i+=2){
    bool isPrim=1; //isPrim Used to determine 1 Whether the number is prime or not 
    for(int j=0;j<primNum;j++){
      times++;
      if(i%prim[j]==0){
        isPrim=0;
        break; // Don't add break Before,   when n=10 0000 When, times=2 5239 6936 time   ( 2.5 Million)   After adding times=4626 4478 time   ( 4.5 Ten million times)  
      }
      
    } 
    if(isPrim) prim[primNum++]=i;// If it is a prime number, it is stored prim A prime number array  
  } 
  return prim[primNum-1];
} 

/*
   methods 2 :   Backward - forward integer enumeration 
   And the method 2 Less space consumption  
   
   when n=10 0000 When, 
  ans=99991
  times=346 time  

   when n=100 0000 ", use the method 1 You can't figure it out at all  
  ans=99 9983
  times=1811 time  
  
   when n=1 0000 0000(1 Hundred million ) When,  
  ans=9999 9989
  times=11314 time  
  
   when n=10 0000 0000(10 Hundred million ) When,  
  ans=9 9999 9937
  times=52537 time  
*/
bool isPrimMothed(int n){
  bool isPrim=1; //isPrim Used to determine 1 Whether the number is prime or not 
  if(n==2||n==3) return 1;
  for(int i=2;i*i<=n;i++){
    times++;
    if(n%i==0) return 0;
  } 
  return 1;
} 

int primLessN_2(int n){
  for(int i=n;i>=2;i--){
    if(isPrimMothed(i)) return i;
  } 
}
int main(){
  int n;
  scanf("%d",&n);
  //int ans=primLessN(n);
  int ans=primLessN_2(n);
  cout<<ans<<endl; 
  printf(" Total judgment frequency times:%d\n",times); 
  printf(" The total number of primes primNum:%d\n",primNum); 
  return 0;
}

Thank you for reading, I hope to help you, thank you for your support of this site!