Skip to content

Instantly share code, notes, and snippets.

@kyrathasoft
Created May 16, 2021 13:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kyrathasoft/90c933db99945ec0ceed4e85fcd28ba4 to your computer and use it in GitHub Desktop.
Save kyrathasoft/90c933db99945ec0ceed4e85fcd28ba4 to your computer and use it in GitHub Desktop.
an efficient method for detecting if a positive integer is a prime number
/* This code written by Bryan Miller 9th May 2021, but the actual prime detection
methods contain code found on various websites and forums.
To create DLL prime.dll, csc /t:library prime.cs
To build EXE myprogram.exe referencing that DLL, csc /r:prime.dll myprogram.cs */
using System;
namespace IsPrimeNs {
public class IsPrimeCls {
public static bool IsPrime(int n){
if (n == 1) return false;
if (n == 2 || n == 3 || n == 5) return true;
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
var boundary = (int)Math.Floor(Math.Sqrt(n));
// You can do less work by observing that at this point, all primes
// other than 2 and 3 leave a remainder of either 1 or 5 when divided by 6.
// The other possible remainders have been taken care of.
int i = 6; // start from 6, since others below have been handled.
while (i <= boundary)
{
if (n % (i + 1) == 0 || n % (i + 5) == 0)
return false;
i += 6;
}
return true;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment