Filter method C++ implementation

Screening method

Introduction:
Screening method, also known as screening method, is to find no more than the natural number N (N > A method of all primes of 1). It is said to have been invented by the ancient Greek Eratosthenes (c. 274-194 BC), also known as the Eratosthenes sieve.

Here's how: put N natural Numbers in order. 1 is not prime, it's not composite, cross it out. The second number, 2, is left over as the prime, and you cross out everything that's divisible by 2. The first uncrossed out number after 2 is 3, leave the 3, and then cross out all the Numbers after 3 that are divisible by 3. The first uncrossed out number after 3 is 5, leave the 5, and then cross out all the Numbers that are divisible by 5. And if you keep doing that, you're going to sieve out all the combinations that don't exceed N, and you're going to be left with all the primes that don't exceed N. Because the greeks wrote Numbers on wax plates, and when each number was crossed out, they wrote small dots on it. When the search for prime Numbers was finished, the dots looked like a sieve. (another explanation is that the Numbers were written on a papyrus, and each time a number was crossed out, the number was cut out. When the search for prime Numbers was finished, the small holes acted like a sieve.)

Use C++ to implement the filtering method:
Take the example of finding primes within 100 by screening

#include<iostream>
using namespace std;
int main()
{
 int i,j,a[101];//The 101 size array is defined here to correspond to the natural number, that is, a[2] corresponds to the natural number 2
 for(i=2;i<100;i++) 
     a[i]=1;//Completes the initialization of the array
 for(i=2;i<100;i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//The corresponding multiples are excluded
  }
 } 
 //Perform an output operation
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'t';
 } 
 cout<<endl;
 return 0;
} 

Some thinking and optimization
In the past, when learning the algorithm for calculating prime Numbers, there was a general optimization algorithm.

Also is to use

for(i=1;i<(j/2);i++)

or

for(i=1;i<sqrt(j);i++)//Using the SQRT () function involves importing the math.h header file

To replace the

for(i=1;i<j;i++)

It can significantly reduce the complexity of the algorithm

At the beginning of direct use, do not know what is the principle. Then I looked at it, and it turned out to be this:

Take SQRT (j) instead of I as an example

The most basic way to find a prime is to divide by I all the integers between 2 and j-1. If neither is divisible, it is prime.

And I = SQRT (j) * SQRT (j)

We divide I by all integers between 2 and SQRT (j), which covers all integers between 2 and I minus 1.

Set 2 < K. < SQRT (j), then if j%k==0, then SQRT (j) < M = (j % k) < J - 1.

In other words, since we're dividing by division, we're dividing by a smaller divisible thing, but we're dividing by a larger divisible thing.

Optimized code:

#include<iostream>
#include<math.h> 
using namespace std;
int main()
{
 int i,j,a[101];//The 101 size array is defined here to correspond to the natural number, that is, a[2] corresponds to the natural number 2
 for(i=2;i<100;i++) 
     a[i]=1;//Completes the initialization of the array
 for(i=2;i<sqrt(100);i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//The corresponding multiples are excluded
  }
 } 
 //Perform an output operation
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'t';
 } 
 cout<<endl;
 return 0;
}