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−−−−−−−√, eliminating Number / 2half 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;