Description:-
A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
1. Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, … ; the p itself should not be marked ).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
Code Implementation :-
<br />#include<iostream>
#include <cstring>
#include <ctime>
#include <cstdio>
using namespace std;
int markprime(bool arr[], int n, int i) {
int x = 2, p;
while((p = (i * x)) < n) {
arr[p] = true;
++x;
}
x = i+1;
while (arr[x]) x++;
return x;
}
int main(){
int n, i;
i = 2;
cout<<"enter the number to which you want to generate the prime numbers-like 100 for 0 - 100"<<endl;
cin >> n;
bool arr[n];
for(int i = 0; i < n; i++) arr[i] = false;
arr[0] = true;
arr[1] = true;
while ((i*i) <= n) {
i = markprime(arr,n,i);
}
for(i = 1; i < n; i++){
if(arr[i] == false)
printf("%d ", i);
}
return 0;
}
Output :-
Myprogworld 