Question

How to find the largest prime factor of a number in C#

Answer 1

using System;

class Program
{
    public static long LargestPrimeFactor(long n) {
        long div = 2, maxPFact = -1;

        while (n != 0) {
            if (n % div != 0)
                div++;
            else {
                maxPFact = n;
                n /= div;
                if (n == 1)
                    break;
            }
        }
        return maxPFact;
    }

    static void Main()
    {
        int n = 124;

        Console.WriteLine(LargestPrimeFactor(n)); // 2 x 2 x 31
        Console.WriteLine(LargestPrimeFactor(288)); // 2 x 2 x 2 x 2 x 2 x 3 x 3
        Console.WriteLine(LargestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
        Console.WriteLine(LargestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
    }
}

   
   
/*
run:

31
3
23
5
   
*/

 

70+ SQL courses for beginners and professionals

Answer 2

using System;

public class Program
{
    // Returns the largest prime factor of n
    public static long LargestPrimeFactor(long n) {
        long largest = -1;

        // Step 1: Remove all factors of 2
        while (n % 2 == 0) {
            largest = 2;
            n /= 2;
        }

        // Step 2: Try odd factors from 3 to sqrt(n)
        for (long i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                largest = i;
                n /= i;
            }
        }

        // Step 3: If n is still > 2, it is a prime number
        if (n > 2) {
            largest = n;
        }

        return largest;
    }

    public static void Main(string[] args)
    {
        int n1 = 124; // 2 x 2 x 31
        int n2 = 288; // 2 x 2 x 2 x 2 x 2 x 3 x 3
        int n3 = 1288; // 2 x 2 x 2 x 7 x 23
        int n4 = 100000000; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
        long n5 = 600851475143; // 71, 893, 1471, 6857

        Console.WriteLine("Largest prime factor: " + LargestPrimeFactor(n1));
        Console.WriteLine("Largest prime factor: " + LargestPrimeFactor(n2));
        Console.WriteLine("Largest prime factor: " + LargestPrimeFactor(n3));
        Console.WriteLine("Largest prime factor: " + LargestPrimeFactor(n4));
        Console.WriteLine("Largest prime factor: " + LargestPrimeFactor(n5));
    }
}



/*
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

*/

 

70+ SQL courses for beginners and professionals