Prime number problem.
I'm trying to create a simple program that tells me if the number entered is a prime number or not. I'm kind of stuck... I think it the problem is more with the math than the actual program itself. This is what I got:
import java.util.*;
publicclass Ch5Prg7
{
static Scanner console =new Scanner(System.in);
publicstaticvoid main (String[]args)
{
int num;
System.out.println("Enter a positive integer.");
num = console.nextInt();
if (num == 1){System.out.println("That number is not prime.");}
if (num == 2){System.out.println("That number is prime.");}
if (num > 2){
// not sure what to do here
}
}
}
Yeah, I know. It's not much. I just don't really know where to begin. Any help with the math or anything in general would be greatly appreciated. :)
[1633 byte] By [
JimboPa] at [2007-10-2 4:21:18]
Well, i don't know if you've found the solution yet but here is what i've done, it couldn't be the most effcient algorithm becuase i'm just high school student:
import java.io.*;
public class FindPrimeNumbers
{
public static void main() throws IOException {
int factor = 0;
BufferedReader input = new BufferedReader (new InputStreamReader(System.in)); //allows input
System.out.print("Please enter a positive interger : ");
int num = Integer.parseInt(input.readLine());
if (num == 1){
System.out.println("That number is not prime.");
}else{
for (int i = 1; i <= num; i++) {
for (int m = 2; m <= num; m++) {
if (m != i) {
if (i % m == 0) { factor = factor + 1; }
}
}
factor = 0;
}
if (factor == 0)
System.out.println(num +" is a prime number");
else
System.out.println(num +" is not a prime number");
}
}
}
A suggestion: When you first time ask for the input you could add some flags in your code to make sure that you're only getting the positive integer, nothing else (e.g. stirng, double, -number etc.).
I hope that helps!!
Hi,
After changing main() to main(String[]), I found it told me that
everything except 1 was prime...
The pair of nested loops is more than is needed. Just use a single
loop that looks at each candidate and if it's a factor of num we're
finished. We don't really need to look at everything up to num (for
example we know that 105 isn't a factor 106) - how far should we
search?
Cheers,
Peter
First, I advise you to do some reading in this subject. It can get quite interesting.anyway, you can make sure a number is prime if it doesn't devide in the numbers from 2 to its square root.
> Hi,
>
> After changing main() to main(String[]), I found it
> told me that
> everything except 1 was prime...
why that affect though? I don't understand?
I don't think that's reason, the whole algorithm is wrong. The program tells you that every number except 1 is prime because i'm reseting the valve of factor back to zero at the end of the loop.
for (int i = 1; i <= num; i++) {
for (int m = 2; m <= num; m++) {
if (m != i) {
if (i % m == 0) { factor = factor + 1; }
}
}
[b]factor = 0;[/b]
}
>
> The pair of nested loops is more than is needed.
> Just use a single
> loop that looks at each candidate and if it's a
> factor of num we're
> finished. We don't really need to look at everything
> up to num (for
> example we know that 105 isn't a factor 106) - how
> far should we
> search?
ok i understand what you're trying to say but what will be the end condition of the loop. Here is something i came up after reading your reply:
public static void main(String args[]) throws IOException {
int factor = 0;
BufferedReader input = new BufferedReader (new InputStreamReader(System.in)); //allows input
System.out.print("Please enter a positive interger : ");
int num = Integer.parseInt(input.readLine());
if (num == 1){
System.out.println("That number is not prime.");
}else{
for (int i = 1; i <?; i++) {
factor = 0;
if (num % i == 0) {
factor ++;
}
}
if (factor == 0)
System.out.println(num +" is a prime number");
else
System.out.println(num +" is not a prime number");
}
}
i believe the most efficient algorithm is to check every number less than or equal to the number in question, starting at 2. that is, for the number 9, try numbers up to 3 starting at 2. this could be implemented as following:
boolean isPrime = false;
if( num > 1 ) {//if this block is skipped, isPrime == false
int root = Math.sqrt( num );//store result to avoid calling every time through loop (every iteration)
for( int divisor = 2; divisor <= root; divisor++ ) {
if( num % divisor == 0 ) {
isPrime = false;//number is NOT prime
break; //no need to continue loop
}
}
}
if( isPrime ) {
System.out.println("That number is prime.");
}
else {
System.out.println("That number is not prime.");
}
Another algorithm you could use, although it may be slower due to the allocation of the array would be:
boolean isPrime = false;
if( num > 1 ) {//if this block is skipped, isPrime == false
int root = (int)Math.sqrt( num );//store result to avoid calling every time through loop (every iteration)
bool[] possibleFactors = new int[ root + 1 ];
//all array elements are initialized to false by the Java VM
//false indicates untested value, true indicates tested value
for( int divisor = 2; divisor <= root; divisor++ ) {
if( possibleFactors[ divisor ] == false ) {
if( num % divisor == 0 ) {
isPrime = false;//number is NOT prime
break;//no need to continue loop
}
else {
//set all multiples of divisor to true (indicating they were tested) since
//none of the multiples will divide evenly if one of there factors didn't
for( int i = divisor; i <= root; i += divisor ) {
possibleFactors[ i ] = true;
}
}
}
}
}
if( isPrime ) {
System.out.println("That number is prime.");
}
else {
System.out.println("That number is not prime.");
}
@modia at 2007-7-15 23:47:54 >
Generally you want to use subroutines to modularize your code:
Here is a simple prime routine - just one case after another:
public static boolean prime(int p){
if(p<2) return false; // negatives and 1 are not prime
if(p==2) return true; // 2 is prime
if(p%2==0)return false; // all other evens are not prime
for(int i=3; i*i<=p; i+=2) {if(p%i==0) return false;} // if odd p has odd factor it is not prime
return true; // otherwise it is odd and has no factors so is prime.
}
then you can use this routine in your main routine to print out the desired output
System.out.println(m+ " is" + prime(m)?" ":" not" + "prime.");
salubadsha: yes factor=0 is a bad idea. Why count the factors
anyway?
@modi's (reply 6) first algorithm is what I had in mind. Although
I think it should start isPrime=true. Am I the only one
compiling/running this stuff?
salubadsha: observe how the loop starts at 2, not 1.
We could still do better though. The loop increment
part (divisor++) means we are checking *everything* up
to root. But once we have found that 2 isn't a factor,
why bother checking 4, 6, 8 etc?
Whoops! I've just noticed marlin321 has been there! Maybe
calculating the square root (as an int) is more efficient
than squaring the candidate factor each time. Just a thought
though: can we do better than divisor+=2, given enough special
cases at the start?
Cheers,
Peter
> salubadsha: yes factor=0 is a bad idea. Why count
> the factors
> anyway?
>
> @modi's (reply 6) first algorithm is what I had in
> mind. Although
> I think it should start isPrime=true. Am I the only
> one
> compiling/running this stuff?
>
> salubadsha: observe how the loop starts at 2, not 1.
>
> We could still do better though. The loop increment
> part (divisor++) means we are checking *everything*
> up
> to root. But once we have found that 2 isn't a
> factor,
> why bother checking 4, 6, 8 etc?
>
> Whoops! I've just noticed marlin321 has been there!
> Maybe
> calculating the square root (as an int) is more
> efficient
> than squaring the candidate factor each time. Just a
> thought
> though: can we do better than divisor+=2, given
> enough special
> cases at the start?
>
> Cheers,
>
> Peter
Thanks guys that was really helpful. I was trying to help the other guy but i learned a lot from you both (Peter & @modi). I'm pretty sure in future i won't have any problems with this sort of algorithm.
Regards,
M.salman
Is it mathematically proved that every divisor of a number greater than its square root is a product of prime factors we already checked?R. Hollenstein
Hi Robin,
> Is it mathematically proved that every divisor of a
> number greater than its square root is a product of
> prime factors we already checked?
No. It's not true either.
For instance 17 is a divisor of 136 and is bigger than
11-and-a-bit, but it's not a product of *any* (smaller)
primes. Of course if we were checking 136 for primeness
we would have stopped before we got to 17.
The point is that factors come in pairs:
2x68
4x34
8x17
The first is always less than the square root, the second
always greater. It *is* quite easy to prove that every
factor greater than the square root has a partner which
is less than the square root. (Consider what would happen
if the factor and its partner were both greater...) And that's
why the loop only has to go as far as the square root.
Cheers,
Peter
>@modi's (reply 6) first algorithm is what I had in mind. Although
>I think it should start isPrime=true. Am I the only one
>compiling/running this stuff?
sorry, isPrime should start as true. that was a careless error on my part.
this is what the correct code should look like:
boolean isPrime = true;
if( num > 1 ) {//if this block is skipped, isPrime == false
int root = Math.sqrt( num );//store result to avoid calling every time through loop (every iteration)
for( int divisor = 2; divisor <= root; divisor++ ) {
if( num % divisor == 0 ) {
isPrime = false;//number is NOT prime
break; //no need to continue loop
}
}
}
if( isPrime ) {
System.out.println("That number is prime.");
}
else {
System.out.println("That number is not prime.");
}
The second algorithm above (in my first post) tests the minimum amount of factors necessary to determine whether or not the number is prime, since it eliminates multiples of already tested numbers. That might not be the best algorithm, however, due to the overhead of allocating the array, and the overhead of travering it after every new factor is tested. It does provide the advantage on certain iterations of only having to test an array variable, as opposed to testing the factor every time, but this advantage is almost certainly negated by the first two disadvantages (especially since the array has to be allocated dynamically).
@modia at 2007-7-15 23:47:54 >
Here is the fastest prime number tester that doesn't allocate an array:
// very simple prime number test
private static boolean isPrime(int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
if (number == 3) return true;
if (number % 3 == 0) return false;
int y = 2;
int x = (int) Math.sqrt(number);
for (int i = 5; i <= x; i += y, y = 6 - y) {
if (number % i == 0)
return false;
}
return true;
}
Yeah, I just cache a list of primes I already found and just loop through that list. There are many other established facts about primes that can abbreviate the process. http://www.planetmath.org has alot of good info.
If the goal of your question is learning, take a look
at the best deterministic method that exists today.
http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf
However, this is academic results only since there are
statistical algorithms that are a lot faster and the
probability for error is so low that other errors like
bugs and bit errors in the processor are drowning the
risk for error due to the algorithm. See method
isProbablePrime(int) at
http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html
parza at 2007-7-20 18:13:40 >
>
> The point is that factors come in pairs:
> 2x68
> 4x34
> 8x17
>
> The first is always less than the square root, the second
> always greater. It *is* quite easy to prove that every
> factor greater than the square root has a partne which
> is less than the square root.
Nitpicking:
Actually the first <= and the second >= the square root.
9 = 3 * 3
public boolean isPrime(int n) {
if(n < 2)
throw new IllegalArgumentException("Please be sensible!");
if(n < 4 || n % 2 == 0)
return true;
int i, limit = (int) Math.sqrt(n);
for(i = 3; i < limit; i += 2)
if(n % i == 0)
return true;
return false;
}
and if you are performing prime number determination many times in a row, one can adopt a "progressive" approach:
// isPrime(int) as defined above
private List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);
private void fillPrimesUpTo(int n) {
for(int i = primes.get(primes.size() - 1) + 2; i <= n; i += 2)
if(isPrime(i))
primes.add(i);
}
public boolean isPrimeFast(int n) {
fillPrimesUpTo((int) Math.sqrt(n));
int i, limit = primes.size();
for(i = 0; i < limit; i++)
if(n % primes.get(i))
return true;
return false;
}
Oops... I made a slip in my argument - in fact you don't rely on isPrime(int) at all!
private List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);
private int nextN = 5;
private void fillPrimesUpTo(int n) {
if(n < nextN)
return;
for(int i = nextN; i <= n; i += 2)
if(isPrimeFast(i))
primes.add(i);
nextN = primes.get(primes.size() - 1) + 2;
}
public boolean isPrimeFast(int n) {
fillPrimesUpTo((int) Math.sqrt(n));
int i, limit = primes.size();
for(i = 0; i < limit; i++)
if(n % primes.get(i))
return true;
return false;
}
Nice try, but no cigar!
I wrote a main routine to test your code and gave it a more appropriate name. Observe the output.
public static boolean bogusIsPrime(int n) {
if(n < 2)
throw new IllegalArgumentException("Please be sensible!");
if(n < 4 || n % 2 == 0)
return true;
int i, limit = (int) Math.sqrt(n);
for(i = 3; i < limit; i += 2)
if(n % i == 0)
return true;
return false;
}
public static void main(String args[]){
System.out.println("Starting");
for(int i = 2; i<20; i++){
System.out.println(i + " - isPrime = " + bogusIsPrime(i));
}
System.out.println("Stoping");
}
Output:
Starting
2 - isPrime = true
3 - isPrime = true
4 - isPrime = true
5 - isPrime = false
6 - isPrime = true
7 - isPrime = false
8 - isPrime = true
9 - isPrime = false
10 - isPrime = true
11 - isPrime = false
12 - isPrime = true
13 - isPrime = false
14 - isPrime = true
15 - isPrime = false
16 - isPrime = true
17 - isPrime = false
18 - isPrime = true
19 - isPrime = false
Stoping
I especially like the result for 15. You'll see why if you fix all the obvious errors.
well that's easy to fix, I guess:
public boolean isPrime(int n) {
if(n < 2)
throw new IllegalArgumentException("Please be sensible!");
if(n < 4 || n % 2 == 0)
return true;
int i, limit = (int) Math.sqrt(n);
for(i = 3; i <= limit; i += 2)
if(n % i == 0)
return false;
return true;
}
> well that's easy to fix, I guess:
Since the OP now has seen almost every solution (incorrect, correct, slow, fast etc.), here's one more:
public boolean isPrimeTheLazyWay(int i) {
if(i < 0) return false;
return (new java.math.BigInteger(Integer.toString(i))).isProbablePrime(100);
}
true - I used this myself for my crypto project last year.
Like JimBo, I'm also having a problem with finding prime numbers. It keeps giving me the error message (PrimalityTester.java:46: missing return statement) right by my primetest method. I'm new to java, so you will notice that the code is simplistic. I would appreciate any suggestions or comments on my coding. We were required to put this in an applet, use the JTextArea with a scroller:
// import java packages
import javax.swing.*;
import java.awt.Container;
public class PrimalityTester extends JApplet
{
public void init()
{
// JTextArea to display prime numbers
JTextArea printPrime = new JTextArea();
// get applet's content pane and attach JTextArea
Container container = getContentPane();
container.add( printPrime );
// attach JTextArea to a JScrollPane so user can scroll results
JScrollPane scroller = new JScrollPane(printPrime);
// set first and second line of text in printPrime
printPrime.setText( "PRIME NUMBERS\n2" );
// loop to test numbers three through 10,000
for (int counter = 3; counter <=10000; counter++ )
if ( primetest(counter)==true )
// append result to JTextArea if true
printPrime.append( "\n" + counter );
}// end method init
// primetest method to test numbers for primality
public boolean primetest( int number )
{
double root=Math.sqrt(number);
// loop to test even divisibility from 2-squareroot of number
for ( int test=2; test <=root; test++ )
// if statement to test even divisibility
if ( number % test==0 )
return false;
} // end primetest method
} // end class PrimalityTester
Well it seems nice algorithm but needs a fix as follows
...
...
// if (n < 4 || n % 2 == 0)
// return true; replace these lines by the code below
if(n<4) return true;
if(n % 2 == 0) return false;
....
....
goita at 2007-7-20 18:13:40 >
You're not returning true if the number is a prime
DaanSa at 2007-7-20 18:13:40 >
> You're not returning true if the number is a primeClarification: this was meant for Leos-Kat
DaanSa at 2007-7-20 18:13:40 >
