Problem

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();
}
}
}
```

Solution

```
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();
}
```

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 ~~ up to an including Number−−−−−−−√$\sqrt{\text{Number}}$, eliminating `Number / 2`

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

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;
```