Program 1 : Finding GCD

Design a program in C to find GCD of two numbers m and n using Eculid’s Method.

Recursive Euclid Method

#include <stdio.h>

int gcdEuclid(int m, int n){
	if (n==0)
		return m;
	return gcdEuclid(n, m%n);
}

int main(){
	int m, n;
	printf("Enter two Integers: ");
	scanf("%d %d", &m, &n);
	 
	int result = gcdEuclid(m, n);
	printf("GCD using Euclid's method: %d\n", result);
	
	return 0;
}

Recursive with Time calculation

#include <stdio.h>
#include <time.h>
int gcdEuclid(int m, int n){
	if (n==0)
		return m;
	return gcdEuclid(n, m%n);
}

int main(){
	int m, n;
	printf("Enter two Integers: ");
	scanf("%d %d", &m, &n);
	 
	clock_t start, end;
	start = clock();
	int result = gcdEuclid(m, n);
	end = clock();
	
	printf("GCD using Euclid's method: %d\n", result);

	double CPU_TIME_USED = ( (double)(end - start)) / CLOCKS_PER_SEC;
	
	printf("Time taken for GCD computation: %f seconds\n", CPU_TIME_USED);

	printf("Time taken for GCD computation: %f milliseconds\n", CPU_TIME_USED * 1000.0);

	
	return 0;
}

Enter two Integers: 48 18

GCD using Euclid's method: 6
Time taken for GCD computation: 0.000000 seconds
Time taken for GCD computation: 0.000000 milliseconds

Iterative Euclid Method

Iterative Euclid Method with time

#include <stdio.h>

int gcdEuclid(int m, int n){
	
	while (n!=0)
	{
		int temp = n;
		n = m%n;
		m = temp; 
	}
	return m;
}

int main(){
	int m, n;
	printf("Enter two Integers: ");
	scanf("%d %d", &m, &n);
	 
	int result = gcdEuclid(m, n);
	printf("GCD using Euclid's method: %d\n", result);
	
	return 0;
}

Design a program in C to find GCD of two numbers m and n using Consective Integer Checking Method.

#include <stdio.h>

int gcdConsecutive(int m, int n) {
    int min = (m < n) ? m : n;
    
    for (int i = min; i >= 1; i--) {
        if (m % i == 0 && n % i == 0)
            return i;
    }
    return 1; // fallback
}

int main() {
    int m, n;
    printf("Enter two integers: ");
    scanf("%d %d", &m, &n);
    
    int result = gcdConsecutive(m, n);
    printf("GCD using Consecutive Integer Checking method: %d\n", result);

    return 0;
}

Design a program in C to find GCD of two numbers m and n using Middle School Method.

#include <stdio.h>

int gcdMiddleSchool(int m, int n) {
    int gcd = 1;
	int min= (m < n ? m : n);
	
    for (int i = 2; i <= min; i++) {
        while (m % i == 0 && n % i == 0) {
            m /= i; // remove it from numbers
            n /= i;
            gcd *= i; // multipy common factor
            min = (m < n ? m : n);
		    
        }
    }
    return gcd;
}

int main() {
    int m, n;
    printf("Enter two integers: ");
    scanf("%d %d", &m, &n);

    int result = gcdMiddleSchool(m, n);
    printf("GCD using Middle School method: %d\n", result);

    return 0;
}

Given two numbers m and n:

1. Start with a divisor i = 2 (the smallest prime number).

2. Check if i divides both m and n:

   • If yes:

     • It is a common factor, so multiply it to the gcd.

     • Also, divide both m and n by i to remove that factor.

     • Continue checking i again (don't increment yet) — because the same prime might divide both multiple times (e.g., 2 divides 8 three times).

   • If not:

     • Increment i to check the next number.

3. Stop when i exceeds the smaller of m and n — because no common factor can be larger than the smallest of the two.

Find GCD of 60 and 48

• Prime factorization:

  • 60 = 2 × 2 × 3 × 5

  • 48 = 2 × 2 × 2 × 2 × 3

• Common prime factors: 2 × 2 × 3 = 12