Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Sieve of Eratosthenes
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- int n;
- cin>>n; //input that value till which you want to find the prime numbers.
- vector<int> p(n+1); //creating a vector of n+1 numbers
- for(int i=0;i<=n;i++){
- p[i]=1; // here we will set all elements of vector to 1 first assuming all elements till 0 to n are prime.
- p[0]=p[1]=0; //Now we have set 0th and 1st element to 0 since 0 and 1 are not prime.
- }
- for(int i=2;i<=sqrt(n);i++){
- if(p[i]==1){ //p[i]=1 means that the number is prime.
- for(int j=2;i*j<=n;j++) //Now we are checking that if there is a number in our vector, divisible by n i.e.if j = n/i
- //then we will set that particular element to 0 i.e. p[i*j]=0
- p[i*j]=0;
- }
- }
- vector<int>::iterator it;
- for(it=p.begin();it!=p.end();it++){ //traversing the whole vector
- auto pos = it - p.begin(); // pos is the position
- if(*it==1){
- cout<<pos<<endl; // if the value is one then we will print the distance of that value's index from the beginning and
- // it will be a prime number.
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement