# counting and primes

Gavin Walsh

Greenhorn

Posts: 14

posted 11 years ago

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;

}

}

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

Ranch Hand

Posts: 1228

posted 11 years ago

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:

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 ]

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:

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 ]

[OCA 8 Book] [OCP 8 Book] [Blog] * SCJP (1.4, 1.6) * OCAJP 8 * OCPJP 8

Tom Blough

Ranch Hand

Posts: 263

posted 11 years ago

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,

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,

Tom Blough<br /> <blockquote><font size="1" face="Verdana, Arial">quote:</font><hr>Cum catapultae proscriptae erunt tum soli proscripti catapultas habebunt.<hr></blockquote>