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
8
Medium Priority
?
2,241 Views
Last Modified: 2007-12-19
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
Comment
Question by:rm3
8 Comments
 
LVL 1

Accepted Solution

by:
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
*   a PrimeNumer. {This is the concept of PrimeNumber]
*    
*   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.
*/
public class PrimeNumber {

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

          PrimeNumber pNum = new PrimeNumber();
          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

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

Expert Comment

by:msterjev
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 3

Expert Comment

by:msterjev
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

by:António Sargento
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

by:elstcb
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

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

Expert Comment

by:CleanupPing
ID: 9059040
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.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

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

579 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question