Saleh127

Sieve of Eratosthenes .cpp

May 27th, 2020
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define M 1000000
  4. bool marked[M];
  5. bool isPrime(int n)
  6. {
  7. if (n < 2) return false;
  8. if (n == 2) return true;
  9. if (n % 2 == 0) return false;
  10. if(marked[n] == false) return true; //return marked[n] == false; eitaaa o use koraa jae;
  11. }
  12. void sieve(int n)
  13. {
  14. for (int i = 3; i * i <= n; i += 2)
  15. {
  16. if (marked[i] == false)
  17. {
  18. // i is a prime
  19. for (int j = i * i; j <= n; j += i+i)
  20. {
  21. marked[j] = true;
  22. }
  23. }
  24. }
  25. }
  26. int main()
  27. {
  28. int a,b,i;
  29. cin>>a;
  30. for(i=1;i<=a;i++)
  31. {
  32. sieve(i);
  33. bool c=isPrime(i);
  34. if(c) cout<<i<<" "<<"Prime\n";
  35. else cout<<i<<" "<<"Not Prime\n";
  36. }
  37. return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment