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

**Initialization**: Start with the input integer`N`

that you want to find the largest prime factor of.**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`

.**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`

.**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.

- Check if
- The largest prime factor found during the process is 5.

## Leave a Review