Check if number is prime number
I would just like to ask if this is a correct way of checking if number is prime or not? because I read that 0 and 1 are NOT a prime number.
int num1;
Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
Console.WriteLine(num1 + " is not prime number");
Console.ReadLine();
}
else
{
for (int a = 2; a <= num1 / 2; a++)
{
if (num1 % a == 0)
{
Console.WriteLine(num1 + " is not prime number");
return;
}
}
Console.WriteLine(num1 + " is a prime number");
Console.ReadLine();
}
Solution 1:
var number;
Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());
if (IsPrime(number))
{
Console.WriteLine("It is prime");
}
else
{
Console.WriteLine("It is not prime");
}
public static bool IsPrime(int number)
{
if (number <= 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
var boundary = (int)Math.Floor(Math.Sqrt(number));
for (int i = 3; i <= boundary; i += 2)
if (number % i == 0)
return false;
return true;
}
I changed number / 2 to Math.Sqrt(number) because from in wikipedia, they said:
This routine consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n. If the result of any of these divisions is an integer, then n is not a prime, otherwise it is a prime. Indeed, if n = a*b is composite (with a and b ≠
- then one of the factors a or b is necessarily at most square root of n
Solution 2:
Using Soner's routine, but with a slight variation: we will run until i equals Math.Ceiling(Math.Sqrt(number)) that is the trick for the naive solution:
boolean isPrime(int number)
{
if (number == 1) return false;
if (number == 2) return true;
var limit = Math.Ceiling(Math.Sqrt(number)); //hoisting the loop limit
for (int i = 2; i <= limit; ++i)
if (number % i == 0)
return false;
return true;
}
Solution 3:
Here's a nice way of doing that.
static bool IsPrime(int n)
{
if (n > 1)
{
return Enumerable.Range(1, n).Where(x => n%x == 0)
.SequenceEqual(new[] {1, n});
}
return false;
}
And a quick way of writing your program will be:
for (;;)
{
Console.Write("Accept number: ");
int n = int.Parse(Console.ReadLine());
if (IsPrime(n))
{
Console.WriteLine("{0} is a prime number",n);
}
else
{
Console.WriteLine("{0} is not a prime number",n);
}
}
Solution 4:
I've implemented a different method to check for primes because:
- Most of these solutions keep iterating through the same multiple unnecessarily (for example, they check 5, 10, and then 15, something that a single % by 5 will test for).
- A % by 2 will handle all even numbers (all integers ending in 0, 2, 4, 6, or 8).
- A % by 5 will handle all multiples of 5 (all integers ending in 5).
- What's left is to test for even divisions by integers ending in 1, 3, 7, or 9. But the beauty is that we can increment by 10 at a time, instead of going up by 2, and I will demonstrate a solution that is threaded out.
- The other algorithms are not threaded out, so they don't take advantage of your cores as much as I would have hoped.
- I also needed support for really large primes, so I needed to use the BigInteger data-type instead of int, long, etc.
Here is my implementation:
public static BigInteger IntegerSquareRoot(BigInteger value)
{
if (value > 0)
{
int bitLength = value.ToByteArray().Length * 8;
BigInteger root = BigInteger.One << (bitLength / 2);
while (!IsSquareRoot(value, root))
{
root += value / root;
root /= 2;
}
return root;
}
else return 0;
}
private static Boolean IsSquareRoot(BigInteger n, BigInteger root)
{
BigInteger lowerBound = root * root;
BigInteger upperBound = (root + 1) * (root + 1);
return (n >= lowerBound && n < upperBound);
}
static bool IsPrime(BigInteger value)
{
Console.WriteLine("Checking if {0} is a prime number.", value);
if (value < 3)
{
if (value == 2)
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
else
{
Console.WriteLine("{0} is not a prime number because it is below 2.", value);
return false;
}
}
else
{
if (value % 2 == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by 2.", value);
return false;
}
else if (value == 5)
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
else if (value % 5 == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by 5.", value);
return false;
}
else
{
// The only way this number is a prime number at this point is if it is divisible by numbers ending with 1, 3, 7, and 9.
AutoResetEvent success = new AutoResetEvent(false);
AutoResetEvent failure = new AutoResetEvent(false);
AutoResetEvent onesSucceeded = new AutoResetEvent(false);
AutoResetEvent threesSucceeded = new AutoResetEvent(false);
AutoResetEvent sevensSucceeded = new AutoResetEvent(false);
AutoResetEvent ninesSucceeded = new AutoResetEvent(false);
BigInteger squareRootedValue = IntegerSquareRoot(value);
Thread ones = new Thread(() =>
{
for (BigInteger i = 11; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
onesSucceeded.Set();
});
ones.Start();
Thread threes = new Thread(() =>
{
for (BigInteger i = 3; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
threesSucceeded.Set();
});
threes.Start();
Thread sevens = new Thread(() =>
{
for (BigInteger i = 7; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
sevensSucceeded.Set();
});
sevens.Start();
Thread nines = new Thread(() =>
{
for (BigInteger i = 9; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
ninesSucceeded.Set();
});
nines.Start();
Thread successWaiter = new Thread(() =>
{
AutoResetEvent.WaitAll(new WaitHandle[] { onesSucceeded, threesSucceeded, sevensSucceeded, ninesSucceeded });
success.Set();
});
successWaiter.Start();
int result = AutoResetEvent.WaitAny(new WaitHandle[] { success, failure });
try
{
successWaiter.Abort();
}
catch { }
try
{
ones.Abort();
}
catch { }
try
{
threes.Abort();
}
catch { }
try
{
sevens.Abort();
}
catch { }
try
{
nines.Abort();
}
catch { }
if (result == 1)
{
return false;
}
else
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
}
}
}
Update: If you want to implement a solution with trial division more rapidly, you might consider having a cache of prime numbers. A number is only prime if it is not divisible by other prime numbers that are up to the value of its square root. Other than that, you might consider using the probabilistic version of the Miller-Rabin primality test to check for a number's primality if you are dealing with large enough values (taken from Rosetta Code in case the site ever goes down):
// Miller-Rabin primality test as an extension method on the BigInteger type.
// Based on the Ruby implementation on this page.
public static class BigIntegerExtensions
{
public static bool IsProbablePrime(this BigInteger source, int certainty)
{
if(source == 2 || source == 3)
return true;
if(source < 2 || source % 2 == 0)
return false;
BigInteger d = source - 1;
int s = 0;
while(d % 2 == 0)
{
d /= 2;
s += 1;
}
// There is no built-in method for generating random BigInteger values.
// Instead, random BigIntegers are constructed from randomly generated
// byte arrays of the same length as the source.
RandomNumberGenerator rng = RandomNumberGenerator.Create();
byte[] bytes = new byte[source.ToByteArray().LongLength];
BigInteger a;
for(int i = 0; i < certainty; i++)
{
do
{
// This may raise an exception in Mono 2.10.8 and earlier.
// http://bugzilla.xamarin.com/show_bug.cgi?id=2761
rng.GetBytes(bytes);
a = new BigInteger(bytes);
}
while(a < 2 || a >= source - 2);
BigInteger x = BigInteger.ModPow(a, d, source);
if(x == 1 || x == source - 1)
continue;
for(int r = 1; r < s; r++)
{
x = BigInteger.ModPow(x, 2, source);
if(x == 1)
return false;
if(x == source - 1)
break;
}
if(x != source - 1)
return false;
}
return true;
}
}
Solution 5:
This is basically an implementation of a brilliant suggestion made by Eric Lippert somewhere above.
public static bool isPrime(int number)
{
if (number == 1) return false;
if (number == 2 || number == 3 || number == 5) return true;
if (number % 2 == 0 || number % 3 == 0 || number % 5 == 0) return false;
var boundary = (int)Math.Floor(Math.Sqrt(number));
// 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 (number % (i + 1) == 0 || number % (i + 5) == 0)
return false;
i += 6;
}
return true;
}