• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Prime Numbers g-stoyanov   Jun 27th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top