Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace Problem_0003
- {
- using System;
- using System.Diagnostics;
- /// <summary>
- /// Largest prime factor
- /// Problem 3
- /// The prime factors of 13195 are 5, 7, 13 and 29.
- /// What is the largest prime factor of the number 600851475143 ?
- /// </summary>
- class Program
- {
- static void Main(string[] args)
- {
- Stopwatch watch = Stopwatch.StartNew();
- ulong number = 600851475143;
- ulong boundary = (ulong)Math.Floor(Math.Sqrt(number));
- ulong largestPrimeFactorResult = 0;
- for (ulong i = boundary; i > 1; i--)
- {
- if (number % i == 0 && IsPrime(i))
- {
- largestPrimeFactorResult = i;
- break;
- }
- }
- watch.Stop();
- decimal elapsedSeconds = watch.ElapsedMilliseconds / 1000;
- Console.WriteLine($"Result : {largestPrimeFactorResult}");
- Console.WriteLine($"Execution time: {elapsedSeconds}");
- }
- public static bool IsPrime(ulong number)
- {
- if (number <= 1)
- {
- return false;
- }
- if (number == 2 || number == 3 || number == 5)
- {
- return true;
- }
- if ((number & 1) == 0)
- {
- return false;
- }
- if (number % 5 == 0)
- {
- return false;
- }
- ulong boundary = (ulong)Math.Floor(Math.Sqrt(number));
- ulong reminder = number % 6;
- if (reminder == 0 || reminder == 2 || reminder == 3 || reminder == 4)
- {
- return false;
- }
- else
- {
- for (ulong i = 6; i < boundary; i += 6)
- {
- if (number % (i + 1) == 0)
- {
- return false;
- }
- if (number % (i + 5) == 0)
- {
- return false;
- }
- }
- }
- return true;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement