C and C++ example of a method for calculating prime Numbers by filtering

What is prime number

The prime number refers to the number whose factor is only 1 and itself (1 is not a prime number). Solving the prime number is very widely used in mathematics, and solving the prime number within n is also a problem we often encounter in programming. In this problem, the screening method can solve the prime number very quickly.

i is any number between 2 and n minus 1. n is not prime if it is divisible, otherwise it is prime

According to sieve method

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

The specific approach is as follows:

Put the natural Numbers N in order. 1 is not prime or composite. Cross it out. The second number, 2, is prime, and you cross out everything that's divisible by 2. The first uncrossed out number after 2 is 3, keep the 3, and cross out all the Numbers after 3 that are divisible by 3. The first uncrossed out number after 3 is 5, keep the 5, and cross out all the Numbers that are divisible by 5. If you keep going like this, you will sieve out all the composites that do not exceed N, leaving behind all the primes that do not exceed N. Because the greeks wrote the Numbers on wax plates, and marked them with dots for each number they crossed out. When they had finished their work of finding prime Numbers, the dots looked like a sieve, so they called the Eratosthenes sieve, or the sieve method for short. (another explanation is that the number was written on a papyrus, and for each number to be crossed out, the number was cut out. When the search for prime Numbers was finished, the many small holes looked like a sieve.)

General enumeration method:

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
bool isPlain(int x){
 if(x<2) return false;
 else{
 for(int i=2;i<x;i++)
 {
 if(!(x%i))
 return false;
 }
 }
 return true;
}
int main()
{
 int n;
 cin>>n;
 int cot=0;
 for(int j=0;j<n;j++){
 if(isPlain(j)){
 cout<<j<<((++cot%7==0)?"\n":"\t");
 }
 }
}

Screening method:

Original version:

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
 int n;
 cin>>n;
 bool* ans=new bool[n];
 memset(ans,true,sizeof(bool)*n);//
 ans[0]=false;
 ans[1]=false;
 for(int i=2;i<n;i++){
 if(ans[i]){
 for(int j=i*2;j<n;j+=i){// Multiple integer 
 ans[j]=false;
 }
 }
 }
 int col = 0;
 for(int i=0;i<n;i++){
 if(ans[i]){
 cout<<i<<" ";
 }
 }
 return 0;
}

Improved version

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;
int main()
{
 int n;
 cin>>n;
 bitset<100000> ans;
 ans.set(0);
 ans.set(1);
 for(int j=2; j<=sqrt(n); j++)
 {
 for(int i=2*j; i < n; i+=j)
 {
 ans.set(i);
 }
 }
 int cot=0;
 for(int i=0; i<n; i++)
 {
 if(ans[i]!=1)
 {
 cout<<i<<((++cot%7==0)?"\n":"\t");
 }
 }
}

conclusion