Return to Answer

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

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

The for-loop iterations could be reduced by 75%. You only need to test factors up to Number / 2, eliminating half the loop. Furthermore, since 2 is the only even prime, you can skip all subsequent even candidates, eliminating another half.

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.

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 75%. You only need to test factors up to Number / 2, eliminating half 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 < n / 2; 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.

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 75%. You only need to test factors up to Number / 2, eliminating half 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.