Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. //Sieve of Eratosthenes
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int main(){
  5. int n;
  6. cin>>n; //input that value till which you want to find the prime numbers.
  7. vector<int> p(n+1); //creating a vector of n+1 numbers
  8. for(int i=0;i<=n;i++){
  9. p[i]=1; // here we will set all elements of vector to 1 first assuming all elements till 0 to n are prime.
  10. p[0]=p[1]=0; //Now we have set 0th and 1st element to 0 since 0 and 1 are not prime.
  11. }
  12. for(int i=2;i<=sqrt(n);i++){
  13. if(p[i]==1){ //p[i]=1 means that the number is prime.
  14. 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
  15. //then we will set that particular element to 0 i.e. p[i*j]=0
  16. p[i*j]=0;
  17. }
  18. }
  19. vector<int>::iterator it;
  20. for(it=p.begin();it!=p.end();it++){ //traversing the whole vector
  21. auto pos = it - p.begin(); // pos is the position
  22. if(*it==1){
  23. cout<<pos<<endl; // if the value is one then we will print the distance of that value's index from the beginning and
  24. // it will be a prime number.
  25. }
  26. }
  27. return 0;
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement