Guest User

Euclid Eratosthene

a guest
Oct 28th, 2016
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.40 KB | None | 0 0
  1. // Euclid
  2. int gcd(int a, int b) {
  3.     if (b == 0) return a;
  4.     return gcd(b, a % b);
  5. }
  6.  
  7. //Eratosthene
  8. void eratosthene() {
  9.     for (int i = 0; i < N; i++) {
  10.         prime[i] = true;
  11.     }
  12.     prime[1] = false;
  13.     for (int i = 2; i < N; i++) {
  14.         for (int j = i * i; j < N; j += i) {
  15.             prime[j] = false;
  16.         }
  17.     }
  18.     //print prime numbers
  19.     for (int i = 2; i < N; i++) {
  20.         if (prime[i]) cout << i << " ";
  21.     }
  22. }
Advertisement
Add Comment
Please, Sign In to add comment