Advertisement
g-stoyanov

Prime Numbers

Jun 27th, 2019
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.24 KB | None | 0 0
  1. namespace Problem_0003
  2. {
  3.     using System;
  4.     using System.Diagnostics;
  5.  
  6.     /// <summary>
  7.     /// Largest prime factor
  8.     /// Problem 3
  9.     /// The prime factors of 13195 are 5, 7, 13 and 29.
  10.     /// What is the largest prime factor of the number 600851475143 ?
  11.     /// </summary>
  12.     class Program
  13.     {
  14.         static void Main(string[] args)
  15.         {
  16.             Stopwatch watch = Stopwatch.StartNew();
  17.  
  18.             ulong number = 600851475143;
  19.             ulong boundary = (ulong)Math.Floor(Math.Sqrt(number));
  20.  
  21.             ulong largestPrimeFactorResult = 0;
  22.  
  23.             for (ulong i = boundary; i > 1; i--)
  24.             {
  25.                 if (number % i == 0 && IsPrime(i))
  26.                 {
  27.                     largestPrimeFactorResult = i;
  28.                     break;
  29.                 }
  30.             }
  31.  
  32.             watch.Stop();
  33.             decimal elapsedSeconds = watch.ElapsedMilliseconds / 1000;
  34.  
  35.             Console.WriteLine($"Result        : {largestPrimeFactorResult}");
  36.             Console.WriteLine($"Execution time: {elapsedSeconds}");
  37.         }
  38.  
  39.         public static bool IsPrime(ulong number)
  40.         {
  41.             if (number <= 1)
  42.             {
  43.                 return false;
  44.             }
  45.  
  46.             if (number == 2 || number == 3 || number == 5)
  47.             {
  48.                 return true;
  49.             }
  50.  
  51.             if ((number & 1) == 0)
  52.             {
  53.                 return false;
  54.             }
  55.  
  56.             if (number % 5 == 0)
  57.             {
  58.                 return false;
  59.             }
  60.  
  61.             ulong boundary = (ulong)Math.Floor(Math.Sqrt(number));
  62.  
  63.             ulong reminder = number % 6;
  64.  
  65.             if (reminder == 0 || reminder == 2 || reminder == 3 || reminder == 4)
  66.             {
  67.                 return false;
  68.             }
  69.             else
  70.             {
  71.                 for (ulong i = 6; i < boundary; i += 6)
  72.                 {
  73.                     if (number % (i + 1) == 0)
  74.                     {
  75.                         return false;
  76.                     }
  77.  
  78.                     if (number % (i + 5) == 0)
  79.                     {
  80.                         return false;
  81.                     }
  82.                 }
  83.             }
  84.  
  85.             return true;
  86.         }
  87.     }
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement