?
Solved

Prime number algorithm

Posted on 2003-02-27
8
Medium Priority
?
2,238 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

 
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

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

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

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
Suggested Courses
Course of the Month10 days, 8 hours left to enroll

765 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