asked on

Prime number algorithm

I need to write a method or function that accepts a numeric argument and returns a boolean true if the number is a prime number and false if it is not.

Also I would like it to be as accurate as possible, preferably in the 99.999% range (may need the Miller-Rabin test but this is only a suggestion I do not fully understand this test myself).

It will also require minimal processing resources. Therefore the method should break as soon as the first test fails.

I prefer it be in Java and have comments to explain the algorithm and math or it will be useless to me. (If I cant understand the math no points will be awarded).

This will require both math and programming expertise therefore it is listed as 200pts. Both processing resources reqiured and accuracy will be considered for rewarding points.

Thank You ahead of time. I could not do this on my own.

ASKER CERTIFIED SOLUTION

socratesk

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

msterjev

You should construct a BigInteger object and call it's method isProbablyPrime();

msterjev

import java.math.BigInteger;

public class Test
{
public static void main(String[] args)
{
int i;
try
{
i=Integer.parseInt(args[0]);
BigInteger bi=BigInteger.valueOf(i);
if(bi.isProbablePrime(100))
{
System.out.println(i+" is probably prime!");
}
else
{
System.out.println(i+" is not probably prime!");
}
}
catch(Exception e)
{
e.printStackTrace();
}
}
}

msterjev

Or if you want to deal directly with the algorithm, the first optimization is that the upper bound for checking should Math.sqrt(number) not number/2;

António Sargento

Here you could find a prime test algorithm that could answer to your question.
http://mathworld.wolfram.com/news/2002-08-07_primetest/
http://www.cse.iitk.ac.in/primality.pdf

elstcb

to further the discussion on algorithm optimization, you could also make sure that the number is odd. If it's even then it will be divisable by 2!

use something like:
if (number%2 == 0) {
System.out.println("number is even, therefore not a prime");
}

elstcb

lol just thought check for divisible by 5 as well... that eliminates quite a few as well

CleanupPing

rm3:
This old question needs to be finalized -- accept an answer, split points, or get a refund. For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations! No comment means you don't care.