Largest prime factor

Problem 3 

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number N

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public class Problem3
    {
        public static void Function()
        {
            int t = Convert.ToInt32(Console.ReadLine());
            for (int a0 = 0; a0 < t; a0++)
            {
                long n = Convert.ToInt64(Console.ReadLine());
                
                Console.WriteLine(LargestFactor(n));

            }
        }

        // Normal Life
        static long PrimeFactor(long n)
        {
            long num = 0;
            long i = 1;
            while (++i <= n)
            {
                if (n % i == 0)
                {
                    n/=i;
                    if (IsPrime(i))
                    {
                        num = i;
                    }
                }
            }
            return num;
        }

        static bool IsPrime(long n)
        {
            if(n<2)
            {
                return false;
            }
            
            long i = 2;
            while (i < n)
            {
                if(n% i++ == 0)
                {
                    return false;
                }
            }
            
            return true;
        }


        // Legend Life 
        static long LargestFactor(long n)
        {
            long lastFactor = 0;
            if(n%2==0)
            {
                lastFactor = 2;
                n/=2;
                while (n % 2 == 0)
                {
                    n/=2;
                }
            }
            else
            {
                lastFactor = 1;
            }
            long factor = 3;
            long maxFactor = Convert.ToInt64(Math.Sqrt(n));
            while (n > 1 && factor <= maxFactor)
            {
                if(n % factor == 0)
                {
                    n/=factor;
                    lastFactor=factor;
                    while (n % factor == 0)
                    {
                        n/= factor;
                    }
                    maxFactor = Convert.ToInt64(Math.Sqrt(n));
                }
                factor += 2;

            }
            if (n == 1)
            {
                return lastFactor;
            }
            else
            {
                return n;
            }
        }
    }
Live Code on Paiza.io

Comments

Popular Posts