Advertisement
jelyslime

Simple numbers of Eratosthenes

Jan 16th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. void SieveOfEratosthenes(int n)
  2. {
  3. // Create a boolean array "prime[0..n]" and initialize
  4. // all entries it as true. A value in prime[i] will
  5. // finally be false if i is Not a prime, else true.
  6. bool prime[n+1];
  7. memset(prime, true, sizeof(prime));
  8.  
  9. for (int p=2; p*p<=n; p++)
  10. {
  11. // If prime[p] is not changed, then it is a prime
  12. if (prime[p] == true)
  13. {
  14. // Update all multiples of p greater than or
  15. // equal to the square of it
  16. // numbers which are multiple of p and are
  17. // less than p^2 are already been marked.
  18. for (int i=p*p; i<=n; i += p)
  19. prime[i] = false;
  20. }
  21. }
  22.  
  23. // Print all prime numbers
  24. for (int p=2; p<=n; p++)
  25. if (prime[p])
  26. cout << p << " ";
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement