Algorithms

Question 1

Find the Greatest Common Denominator (GCD) of two numbers

Answer 1

Euclid's Algorithm:
GCD(int a, int b) 
{
    if (b == 0) return a;
    return GCD(b, a%b);
}

Question 2

Find all primes between 1 and N

Answer 2

The Sieve of Eratosthenes:
public boolean[] sieve(int n)
{
    prime = new boolean[n+1]
    Arrays.fill(prime,true);
    prime[0]= false;
    prime[1] = false;
    int m = Math.sqrt(n);

for(i=2; i