Math - Find GCD

Find GCD

// Recursive function to return gcd of a and b

int gcd(int a, int b)

{   

    // Everything divides 0 

    if (a == 0 || b == 0)

       return 0;

    

    // base case

    if (a == b)

        return a;

    

    // a is greater

    if (a > b) 

        return gcd(a-b, b);

    return gcd(a, b-a);

}

Math - Find Prime Factors

/*

Following are the steps to find all prime factors.

1) While n is divisible by 2, print 2 and divide n by 2.

2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.

3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.

*/

int findPrimeFactors(int n, int *arr)

{

    int count = 0;

    int i=0;

    while(n%2 == 0) {

        arr[count++] = 2;

        n/=2;

    }

    for(i=3;i<=sqrt(n);i++) {

        if(n%i == 0) {

            arr[count++] = i;

            n/=i;

        }

    }

    if(n>2)

        arr[count++] = n;

    return count;

}