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