C Program to Find Minimum Prime Factor

Problem: Write a C program to find the minimum prime factor of the given number.

To find the smallest prime factor, we will use the following approach:

1. Input a number.
2. Check which number is the factor of the input number (starting from 2).
3. Then check if that factor is Prime or not.
4. If yes, then that is the minimum prime factor otherwise, repeat the above 2 steps till n/2.

Here is the implementation of the above steps in C:

#include <stdio.h>

int main() {
    int n, i;
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    // Iterate from 2 to n/2
    for (i = 2; i <= n/2; i++) {
        // Check if i is a factor of n
        if (n % i == 0) {
            // Check if i is prime
            int j, is_prime = 1;
            for (j = 2; j <= i/2; j++) {
                if (i % j == 0) {
                    is_prime = 0;
                    break;
                }
            }
            if (is_prime) {
                printf("Minimum prime factor of %d is %d", n, i);
                return 0;
            }
        }
    }

    // If no prime factor was found, n is prime
    printf("%d is prime", n);
    return 0;
}

Output:

Enter a positive integer: 86
Minimum prime factor of 86 is 2

In the above program, after accepting the input from the user, we iterate from 2 to n/2 to find the next smallest factor of the input number (i.e. n).

When the program finds a factor, it then checks whether the factor is prime or not using another for loop.

If the factor turns out to be prime, then we output it as the minimum prime factor of the input number and end the program.

If none of the number in the range (2 to n/2) is a prime factor, then it means the input number is a prime number.