Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Prime number algorithm

Posted on 2003-02-27
Medium Priority
2,241 Views
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.
0
Question by:rm3

LVL 1

Accepted Solution

socratesk earned 600 total points
ID: 8032502
/** A number would be called as a primenumber only if
*   it is divisible by 1 and by that number itself. If
*   is it divisible by any other number, It cannot be
*
*   If a given number is divided by any number, which is
*   greater than 1 and less than that given number and if
*   the reminder is 0, then that given number cannot be
*   a prime number.
*   Because a successful primenumber should not be
*   divisible by any other number. Means.. it should
*   not have any reminder when divided by some number.
*
*   The logic here we used in the below code is.. we need
*   not try checking th given number(n) till n-1 times. If
*   we could do the the checking till n/2 times, this
*   would give us expected result. Because, any checking
*   that is carried out after n/2 times would definitely
*   will have same effect.
*/

/**Main method*/
public static void main(String[] args) {

boolean isPrime = false;     //Initialize the variable here.

int no = Integer.parseInt(args[0]);
isPrime = pNum.isPrimeNo(no);          //Call the actual checking method here.
System.out.println("The given number is " + (isPrime?"":"NOT A ") + "PrimeNumber");
}

private boolean isPrimeNo(int number) {

boolean isPrime = true;          // Is the current number is prime?

// Set isPrime to false, if the number is not prime
for (int divisor = 2; divisor <= number/2; divisor++) {

if (number % divisor == 0) {//If true, the number is not prime
isPrime = false;
break;                         // Exit the for loop
}
}
return isPrime;
}
}
0

LVL 3

Expert Comment

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

LVL 3

Expert Comment

ID: 8032775
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();
}
}
}
0

LVL 3

Expert Comment

ID: 8032899
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;
0

LVL 2

Expert Comment

ID: 8035166
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
0

LVL 2

Expert Comment

ID: 8069264
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");
}
0

LVL 2

Expert Comment

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

Expert Comment

ID: 9059040
rm3:
EXPERTS:
Post your closing recommendations!  No comment means you don't care.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
###### Suggested Courses
Course of the Month12 days, 10 hours left to enroll