# Finding largest prime factor from inputted number

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;

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)
{

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

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

}
}
}

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

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)
{

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

You can exit the loop here because continuing is useless.

break;
}
else
{
i = number;
}
}

}

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: ");

}
}
}

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();
}
• var largestFactor = 0; gives you an Int64?
– Yakk
Commented Jul 23, 2014 at 20:09
• Oh use 0L then.
– user36
Commented Jul 23, 2014 at 20:27

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 Int64 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. Commented Jul 23, 2014 at 17:47
• You only need to check factors up to the square root of n, not up to n/2! Commented Jul 23, 2014 at 19:51
• @Théophile you need to be careful with that. You only need to check up to sqrt(n) in order to check whether n is prime, but that's because if there is a factor greater than sqrt(n), there will also be a corresponding factor less than sqrt(n). There are still factors greater than sqrt(n), so when you're searching for the largest it could be anything up to n/2. For example, 19 * 2 = 38 and 19 > sqrt(38). You could still stop at sqrt(n), but only if you check the corresponding factor greater than sqrt(n) each time you find one less than sqrt(n). Either, neither or both could be prime. Commented Jul 28, 2014 at 12:47
• @Théophile P.S welcome to Code Review! Commented Jul 28, 2014 at 12:50
• @githubphagocyte Yes, when you find a prime p you should of course factor it out and resume the search on n/p and start the iteration at p because there are no smaller prime factors. There are much better algorithms out there, but this will do the trick for small n. (P.S. Thank you! :)) Commented Jul 28, 2014 at 13:36

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;