Printing primes between user-given numbers

Question

I want to display all the prime numbers between two integers taken from the user as input. Also I have to take a user input to specify the number of times the loop should run. Here is the Java code that I have written. I have to now reduce the run-time.

 import java.util.Scanner;
 public class Main{
 private static Scanner x;
 public static void main(String[] args) {
 Scanner x = new Scanner(System.in);
 int num = x.nextInt();
 for (int t = 1; t <= num; t++) {
 int m = x.nextInt();
 int n = x.nextInt();
 if (m >= 1 && n <= 1000000000 && n - m <= 100000) {
 for (int current = m; current <= n; current++) {
 int sqr_root = (int) Math.sqrt(current);
 boolean is_prime = true;
 for (int i = 2; i <= sqr_root; i++) {
 if (current % i == 0) {
 is_prime = false;
 }
 }
 if (is_prime) {
 System.out.println(current);
 }
 }
 }
 }
 }
 }

• TheLostMind: One thing, read the entire line using nextLine() and then split() and parse them as int. I've observed that this will work faster than doing nextInt()several times .

Answer 1

Others have already said to change the algorithm. There are other general coding practice problems that are worth highlighting too.

Naming

Most of the variable names are awful. If I see x, I'll never guess it's a Scanner. m and n for the lower and upper limits are poor names too, as it's easy to mix up which is which. sqr_root and is_prime don't follow the Java convention of using camelCase.

Testing

How do you test that your solution actually works? You rerun the program and enter some inputs and verify that the result is correct? And if you make a change? You recompile, rerun, reverify? That's an awful lot of work. It's a lot less work to write some unit tests instead, which you can easily re-run as simply as the click of a button, and the result is as easy to verify as seeing all green lights or not.

However, to make the implementation unit testable, it needs to change a bit:

• Make the method to take the inputs as parameters instead of standard input
• Make the method return the list of primes found

Something like this:

private static final int MAX_UPPER = 1000000000;
private static final int MAX_DIFF = 100000;
public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 int num = scanner.nextInt();
 for (int t = 1; t <= num; t++) {
 int lower = scanner.nextInt();
 int upper = scanner.nextInt();
 for (Integer prime : getPrimesBetween(lower, upper)) {
 System.out.println(prime);
 }
 }
}
static List<Integer> getPrimesBetween(int lower, int upper) {
 List<Integer> primes = new ArrayList<Integer>();
 if (lower >= 1 && upper <= MAX_UPPER && upper - lower <= MAX_DIFF) {
 for (int current = lower; current <= upper; current++) {
 int squareRoot = (int) Math.sqrt(current);
 boolean isPrime = true;
 for (int i = 2; i <= squareRoot; i++) {
 if (current % i == 0) {
 isPrime = false;
 break;
 }
 }
 if (isPrime) {
 primes.add(current);
 }
 }
 }
 return primes;
}

And some unit tests, to get you started:

@Test
public void testBetween_4_and_5() {
 assertEquals(Arrays.asList(5), getPrimesBetween(4, 5));
}
@Test
public void testBetween_4_and_9() {
 assertEquals(Arrays.asList(5, 7), getPrimesBetween(4, 9));
}

Extract constants

Notice in the example earlier, I converted your original hard-coded constants to proper constants.

private static final int MAX_UPPER = 1000000000;
private static final int MAX_DIFF = 100000;

It's cleaner and better this way.

Correctness

It's not so good that the method returns an empty list if you use a too high input number or too big difference, without any indication that something went wrong. The user might expect a huge list of numbers between 1 and 99999999, or an error, but definitely not an empty list.

Here's a unit test that fails now, until you fix the method to throw an exception in the case of unsupported input values.

@Test(expected = IllegalArgumentException.class)
public void testTooBigDiff() {
 int lower = 11;
 int upper = lower + MAX_DIFF + 1;
 getPrimesBetween(lower, upper);
}

Answer 2

As pointed by Yann4, there are better algorithms, but here are 2 trivial optimizations :

• stop as soon as you know that the number is not prime

• check only for odd number (besides 2)

  // check 2
  boolean is_prime = current % 2 != 0;
  // then odd numbers, stopping as soon a possible
  for (int i = 3; i <= sqr_root && is_prime; i += 2) {
   if (current % i == 0) {
   is_prime = false;
   }
  }
  

on my machine this is more than 20 times faster (mostly because of point 1).

Answer 3

Welcome to Code Review! Here's a simple suggestion to kick-start this:

for (int i = 2; i <= sqr_root; i++) {
 if (current % i == 0) {
 is_prime = false;
 }
}

You should insert a break; once you have determined is_prime is false. This terminates the loop immediately since you know is_prime can't possibly revert to true again for subsequent iterations.

You may also want to look into the algorithm used in the Sieve of Eratosthenes, which filters out non-prime numbers from a sequence. Sounds good for your usage.

For other Java-related suggestions:

1. Please try-with-resource on your Scanner instance, so that it can be safely closed when your program terminates.
2. Consider putting the calculation logic into its own method, so that you can call it by passing it two arguments (start and end). In fact, this can also return a Set of prime numbers for the caller to handle the results (print it out on console, display on a GUI, save to a file, etc.), so that the logic and the input/output of your program are properly separated.
3. Do prompt your user by printing out a descriptive line before the input, e.g.
   • "Enter number of iterations:"
   • "Enter the lower bound (inclusive):"
   • "Enter the upper bound (inclusive):"

Answer 4

You should use a better algorithm. The sieve of eratosthenes is much better for calculating primes.

Run through the algorithm with a very large upper bound (around 10 million is where you'll start finding that there are better methods for calculating primes). Once you've done that, just print out the values within the range that is input by the user.

Disclaimer for following code: Not run as I don't have an IDE to hand, but if I got anything wrong, let me know and I'll edit in.

int maximum = 10000000;
boolean isPrime = new boolean[maximum];
Arrays.fill(isPrime, Boolean.TRUE);
int sqrtRange = Math.sqrt(maximum);
for(int i = 0; i < sqrtRange; ++i)
{
 for(int j = i*2; j < maximum; j += i)
 {
 isPrime[j] = false;
 }
}
//Getting user input ignored here
for(int i = userMin; i < userMax; ++i)
{
 if(isPrime[i])
 {
 System.out.println(i);
 }
}

• Yann: @h.j.k I had left the = true there for clarity, but I was umming about it.
• Martin R: I think it depends. If the program is run with ranges covering the maximum allowed interval (1, 1000000000) then computing the primes upfront with a sieve is probably the best and fastest method. If the program is just called with a single range, e.g. (1000000, 1000020), then checking each number in the range (using a more sophisticated primality test) may be faster.
• h.j.k.: Ah I see... Hope you're ok with the edit.
• Yann: Hm, that could warrant testing @MartinR , I like the idea of on the fly checking, but how would you know which was the 'best' method for a given circumstance? Dividing by each number in between 10000000 and 1000020 is still a lot of checks..
• Yann: @h.j.k. Yeah, it was borderline for me which was the better way to express it, if anyone brought it up I'd have been happy to change it.