Finding largest prime factor from inputted number

Question

This is my first C# console application. This program asks for an input of a number, and finds the highest prime factor of that number. Please review my code.

Have I used things right?
Is my code efficient?
Is there a better way to achieve this?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problems
{
    class Program
    {
        static int FindFactor(Int64 UserInput)
        {
            int LargestFactor = 0;
            Int64 Number = UserInput;

            for (int i = 2; i < Number; i++)
            {
                if (Number % i == 0)
                { 
                    if (PrimeFactorCheck(i) == true)
                    {
                        LargestFactor = i;
                    }
                }
            }
            return LargestFactor;
        }
        static bool PrimeFactorCheck(int Number)
        {
            bool PrimeNumberValidity = true;

            for(int i = 2; i < Number; i++)
            {
                if (PrimeNumberValidity == true)
                {
                    if (Number % i == 0)
                    {
                        PrimeNumberValidity = false;
                    }
                }
                else
                {
                    i = Number;
                }
            }

            return PrimeNumberValidity;
        }
        static void Main(string[] args)
        {
            Console.Write("Hello, please enter a number to find the biggest prime factor of it: ");
             Int64 UserInput = Convert.ToInt64(Console.ReadLine());

            int Answer = FindFactor(UserInput);
            Console.WriteLine(Answer);
            Console.ReadKey();
        }
    }
}

rightfold · Accepted Answer · 2014-07-23 20:27:52Z

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problems
{

You can make this class static since it doesn't make sense to make instances of it.

    static class Program
    {

Local variables are usually not capitalized.

        static int FindFactor(Int64 userInput)
        {

The compiler can infer the type if you use var, so you won't have to repeat it.

            var largestFactor = 0L;
            var number = userInput;

            for (var i = 2; i < number; ++i)
            {

Use && instead of nested if-statements.

                if (number % i == 0 && IsPrimeFactor(i))
                {
                    largestFactor = i;
                }
            }

            return largestFactor;
        }

Usually you put a blank line between function definitions.

Functions returning Booleans are often called "IsBlaBla" instead of "BlaBlaCheck."

        static bool IsPrimeFactor(int number)
        {
            var primeNumberValidity = true;

            for(int i = 2; i < number; ++i)
            {
                if (primeNumberValidity && number % i == 0)
                {
                    primeNumberValidity = false;

You can exit the loop here because continuing is useless.

                    break;
                }
                else
                {
                    i = number;
                }
            }

            return primeNumberValidity;
        }

args is not used, so you can omit it.

        static void Main()
        {
            Console.Write("Hello, please enter a number to find the biggest prime factor of it: ");

            var userInput = Convert.ToInt64(Console.ReadLine());

            var answer = FindFactor(userInput);
            Console.WriteLine(answer);
            Console.ReadKey();
        }
    }
}

You can use LINQ to implement FindFactor in a functional fashion, rather than imperatively.

static int FindFactor(Int64 number) {
    return IEnumerable.Range(2, number - 2)
                      .Where(n => number % n == 0 && IsPrimeFactor(n))
                      .DefaultIfEmpty(0)
                      .Last();
}

Thank you. Any suggestion for me to what to code next? – Hassan Althaf yesterday — Hassan Althaf, yesterday
var largestFactor = 0; gives you an Int64? – Yakk 23 hours ago — Yakk, 23 hours ago

200_success · Answer 2 · 2014-07-23 23:00:54Z

Your algorithm is not only inefficient, it is also incorrect. Let's assume that assume that the PrimeFactorCheck() function works correctly, and just focus on this function:

static int FindFactor(Int64 UserInput)
{
    int LargestFactor = 0;
    Int64 Number = UserInput;

    for (int i = 2; i < Number; i++)
    {
        if (Number % i == 0)
        { 
            if (PrimeFactorCheck(i) == true)
            {
                LargestFactor = i;
            }
        }
    }
    return LargestFactor;
}

First, a nitpick: the renaming of UserInput to Number is pointless. You might as well have named the function parameter properly in the first place.

The function is incorrect, in that it will return 0 if the input is prime. Rather, I would expect it to return the input itself if it is prime.

If the input is an Int64, you should also prepare for the possibility that its largest prime factor also occupies up to 64 bits. ~~You should prefer integral types long or ulong over the System.Int64 structure.~~

One suggestion would be to iterate backwards — for (int i = Number; i > 0; i--) — and return as soon as you find a factor that is prime. That would be a significant optimization, but it still leaves lots of room for improvement.

The for-loop iterations could be reduced by over 75%. You only need to test factors ~~up to Number / 2~~ up to an including \$\sqrt{\textrm{Number}}\$, eliminating ~~half~~ most of the loop. Furthermore, since 2 is the only even prime, you can skip all subsequent even candidates, eliminating another half.

A much better strategy would be to reduce Number every time you encounter a factor. Not only is it sometimes possible to vastly reduce the size of the Number very quickly, you can also avoid PrimeFactorCheck() altogether — and you don't need to be a cryptographer to know that checking whether a large number is prime is computationally intensive.

static ulong FindLargestFactor(Int64 n)
{
    if (n == 2) return 2;
    while (n % 2 == 0) n = n / 2;
    for (Int64 i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0) n = n / i;
    }
    return n;
}

For comparison, my FindLargestFactor(360) only needs to perform 6 modulo-division operations, for a total of 12. Your original FindFactor(360) and its PrimeFactorCheck()s would take 384 modulo operations altogether.

Saying "you should prefer long to Int64" is nonsensical -- they are two different names for the same type. Do not encourage people to use ulong unless they are writing C interop code. Suggest BigInteger if you need an integer bigger than a long. — Eric Lippert, yesterday
You only need to check factors up to the square root of n, not up to n/2! — Théophile, yesterday

ckuhn203 · Answer 3 · 2014-07-23 11:57:13Z

Visual Studio likes to add a bunch of using statements when you create a new console program. You can get rid of these. You're not using Linq or multithreading.

using System.Linq;
using System.Threading.Tasks;

asked	yesterday
viewed	536 times
active	today

current community

your communities

more stack exchange communities

Finding largest prime factor from inputted number

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged c# beginner primes console or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Finding largest prime factor from inputted number

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# beginner primes console or ask your own question.

Related

Hot Network Questions