Advertisement
SteelGolem

finding primes up to 65535 the third strike

Jul 30th, 2020 (edited)
2,430
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.19 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace ConsoleApplication1
  5. {
  6.     class Program
  7.     {
  8.         static List<int> primes;
  9.  
  10.         static void Main(string[] args)
  11.         {
  12.             primes = new List<int>();
  13.  
  14.             // build our primes list
  15.             int max = 65535;
  16.             for (int num = 2; num < max; num++)
  17.             {
  18.                 bool notPrime = false;
  19.                 for (int p = 0; p < primes.Count; p++)
  20.                     if (num % primes[p] == 0) { notPrime = true; break; }
  21.                 if (notPrime) continue;
  22.  
  23.                 primes.Add(num);
  24.                 Console.WriteLine(num + " is a prime.");
  25.             }
  26.  
  27.             Console.WriteLine("there were " + primes.Count + " primes up to " + max + ".");
  28.  
  29.             Console.WriteLine("IsPrime(9001) == " + IsPrime(9001));
  30.  
  31.             Console.ReadKey();
  32.         }
  33.  
  34.         static bool IsPrime(int value)
  35.         {
  36.             // primes is sorted so we can speed up the search using BinarySearch() instead of Contains()
  37.             int index = primes.BinarySearch(value); // SO FAST
  38.             if (index < 0) return false;
  39.             return true;
  40.         }
  41.     }
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement