C# Program to Find the Largest Prime Factor of a Number

This C# program calculates and displays the largest prime factor of a given positive integer. A prime factor is a prime number that divides another number without leaving a remainder.

Problem Statement

Given a positive integer N, your task is to find and return the largest prime factor of N.

C# Program to Find the Largest Prime Factor of a Number

using System;

class Program
{
    static bool IsPrime(long number)
    {
        if (number <= 1)
            return false;
        if (number <= 3)
            return true;

        if (number % 2 == 0 || number % 3 == 0)
            return false;

        for (long i = 5; i * i <= number; i += 6)
        {
            if (number % i == 0 || number % (i + 2) == 0)
                return false;
        }

        return true;
    }

    static long FindLargestPrimeFactor(long number)
    {
        long largestPrimeFactor = 0;

        while (number % 2 == 0)
        {
            largestPrimeFactor = 2;
            number /= 2;
        }

        for (long i = 3; i <= Math.Sqrt(number); i += 2)
        {
            while (number % i == 0)
            {
                largestPrimeFactor = i;
                number /= i;
            }
        }

        if (number > 2)
            largestPrimeFactor = number;

        return largestPrimeFactor;
    }

    static void Main(string[] args)
    {
        Console.Write("Enter a number: ");
        long number = long.Parse(Console.ReadLine());

        long largestPrimeFactor = FindLargestPrimeFactor(number);

        if (largestPrimeFactor == 0)
            Console.WriteLine("No prime factors found.");
        else
            Console.WriteLine($"The largest prime factor of {number} is: {largestPrimeFactor}");
    }
}

How it Works

1. Initialization: Start with the input integer N that you want to find the largest prime factor of.
2. Divide by 2 (if possible): Check if N is divisible by 2 (the smallest prime number). If it is, repeatedly divide N by 2 until it’s no longer divisible by 2. This step is used to remove all the factors of 2 from N.
3. Iterate from 3 onward: Start a loop from 3, and for each number i in the loop, do the following:a. Check if N is divisible by i. If it is, divide N by i.b. If N is not divisible by i, increment i by 2. This is because we only need to check odd numbers as potential factors since even numbers greater than 2 cannot be prime.c. Repeat steps (a) and (b) until N becomes 1 or until i becomes greater than the square root of the remaining N.
4. Result: The largest prime factor of the original input N is the last value of i that was used in the loop.

Here’s a step-by-step example of how this algorithm works for finding the largest prime factor of 60:

• Start with N = 60.
• Divide by 2: N = 30.
• Divide by 2 again: N = 15.
• Start looping from 3.
  • Check if N is divisible by 3: It is, so divide by 3: N = 5.
  • The loop continues to the next value, which is 5.
  • Check if N is divisible by 5: It is, so divide by 5: N = 1.
  • The loop ends because N is now 1.
• The largest prime factor found during the process is 5.

Input/ Output