counting and primes

[Gavin Walsh]

Hi!

So im having trouble with this code, bascially all i need (i think) is some sort of solution to test if a number is a prime...

import java.io.*;

public class prac5prime2try2 {

// main method
public static void main(String args[]) throws IOException {

BufferedReader myInput = new BufferedReader(new InputStreamReader(System.in));

System.out.print("Enter a value: ");
int n = Integer.parseInt(myInput.readLine());
System.out.println("The number entered was "+n);

// loop up to n, and check every number if it's a prime.
for(int i = 1; i <= n; i++) {

if(isPrime(i)) { // this is the same as: if(isPrime(i) == true)
System.out.println (i+" is a prime number");
}
else {
System.out.println (i+" is not a prime number");
}
}
}
*********************this is where i need help********************
// Method to test if a number is prime
private static boolean isPrime(int num) {
if(num < 2) return false;


return true;
}
}

[Srinivasa Raghavan]

Do you get any error on running this code or do you want the logic to implement isPrime() ??
[ November 03, 2005: Message edited by: Srinivasa Raghavan ]

[Mr. C Lamont Gilbert]

lol Dude!

Checking for prime numbers is something that folks create algorithms around. its a big deal to create an efficient check. But its also a common thing in classes I would expect. Try googleing for an algorithm or pay off some math students

[Scott Selikoff]

I'm guessing this is a homework assignment because in practice (as someone suggested) you would NEVER code this by hand, especially for large primes.

There is a method BigInteger.isProbablePrime() which always returns false if the number is not a prime, and returns true if a number is likely prime. So you could:

if(x.isProbablePrime()) {
  // Do a more complex check
} else {
 return false;
}

Since prime numbers are scarse compared to compositive, this would have decent performance depending on how your complex check is written. Although if this is a homework assignment, using isProbablePrime() may not be allowed.
[ November 03, 2005: Message edited by: Scott Selikoff ]

[Tom Blough]

A prime number is a number evenly divisible only by itself and one. So, the easiest method to check for a prime number it to start dividing the number with all integers from two to the number. At each division, it there is a remainder, then check the next number. If the result of the division leaves no remainder, then you have found a component of the number and it is not prime.

After a little more examination you'll find that you do not need to check all the integers less than the given number. You can stop checking at the square root of the given number. Take the number 16. 16 is 1x16, 2x8, 4x4, 8x2, 16x1. You'll notice as soon as I reach the square root of 16, which is four, the components are just reversals of pairs previously found.

To further optimize this operation, recognize that once you divide by two, then there is no need to divide by 4, 6, 8, 10... or any other even number. This same analogy is true for the other integers. If the number is not divisible by 3 then you do not need to check for multiples of 3, etc.

Following the above to it's logical conclusion, you will quickly discover that you only need to check if the given number is divisible by other prime numbers up to the square root of the given number.

Cheers,