Outputting prime numbers in given ranges

Question

I coded an algorithm which shows prime numbers in the ranges provided by the user. The first line states the number of test cases. Example:

INPUT

2 1 10 1 5

OUTPUT

2 3 5 7 2 3 5

t - number of cases, n and m is the range
(t<=10)
m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space

And here is my problem, algorithm works fine, but website which test this, shows- too slow. I need less than 6s !

In my opinion, problem is in method addPrimeNumbers.

class PrimeNumbers{ private static int m = 0; private static int n = 0; private static int t = 0; private static int i = 0; private static String beforeSeparate; private static Scanner sc = new Scanner(System.in); private static List<int[]> scope = new ArrayList<>(); public static void main (String[] args) { t = Integer.valueOf(sc.nextLine()); if (checkT(t)) { beforeSeparate = sc.nextLine(); if (separate(beforeSeparate).length == 2) { m = separate(beforeSeparate)[0]; n = separate(beforeSeparate)[1]; i++; } if (checkM(m) && checkN(n) && t != 1 && n - m <= 100000) { int firstScope[] = {m,n}; scope.add(firstScope); repeatReader(); } else if (t == 1 && checkM(m) && checkN(n) && n - m <= 100000){ int firstScope[] = {m,n}; scope.add(firstScope); } for (int[] aScope : scope) { addPrimeNumbers(aScope[0], aScope[1]); } } } private static void repeatReader(){ beforeSeparate = sc.nextLine(); if (separate(beforeSeparate).length == 2){ m = separate(beforeSeparate)[0]; n = separate(beforeSeparate)[1]; i++; int nextScope[] = {m,n}; scope.add(nextScope); if (i < t){ repeatReader(); } } } private static void addPrimeNumbers(int i, int i1) { String result = ""; for (int j = i; j <= i1 ; j++) { int counters = 0; for (int num = j; num >= i ; num--) { if (j % num == 0){ counters = counters +1; } } if (counters == 2){ result = result + j + "\n"; } } System.out.println(result); } private static boolean checkT(int i){ return i > 0 && i <= 10; } private static boolean checkMinMax(int i) { return i >= 1 && i <= 1000000000; } private static boolean checkM(int i) { return checkMinMax(i) && n > 0 && i <= n; } private static boolean checkN(int i) { return checkMinMax(i) && m > 0 && i >= m; } private static int[] separate(String i){ String twoValue[] = i.split(" "); m = Integer.parseInt(twoValue[0]); n = Integer.parseInt(twoValue[1]); return new int[]{Integer.parseInt(twoValue[0]), Integer.parseInt(twoValue[1])}; } }

Someone know, how to speed up this ?

\$\begingroup\$ Welcome to Code Review! I hope you get some great answers. \$\endgroup\$

Phrancis
– Phrancis

2018-04-28 23:48:56 +00:00
Commented Apr 28, 2018 at 23:48 — Phrancis
– Phrancis, Commented Apr 28, 2018 at 23:48
\$\begingroup\$ Do you happen to know what input causes the problem? \$\endgroup\$

markspace
– markspace

2018-04-29 00:47:48 +00:00
Commented Apr 29, 2018 at 0:47 — markspace
– markspace, Commented Apr 29, 2018 at 0:47

Martin R · Accepted Answer · 2018-04-29 15:20:38Z

Before addressing the performance problem I would like to make some general remarks:

You validate the input values (t, m, n), but invalid numbers are simply ignored. For a programming challenge I would assume that the input values are in the specific ranges. However, if you decide to check the validity then an invalid input should produce an error message or program exception.

Also the check is unnecessary complicated: m and n are passed to functions checkM and checkN, but those functions also refer to the class variables m and n directly. This could be simplified to
```
if (1 <= m && m <= n && n <= 1000000000 && n - m <= 100000) { ... } 
```
Even better, define and use constants for those limits.
The recursive function repeatReader is used to handle all test cases (but only if there is more than one test case). This seems unnecessary complicated to me, a simple loop would suffice.
The logic to get two integers from the input line is duplicated in main and repeatReader.
Several variables are declared as static class variables, but needed only locally in a function (such as m, n, beforeSeparate).
There is no need to store all ranges in an array first, you can read each range and then produce the corresponding output.
Scanner.nextInt() can be used to read the input into integers directly.
In addPrimeNumbers you can print all found prime numbers directly, without concatenating them to a string first.

So the overall structure could be simplified to

import java.util.Scanner; class PrimeNumbers { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int numTests = sc.nextInt(); for (int test = 1; test <= numTests; test++) { int m = sc.nextInt(); int n = sc.nextInt(); printPrimesInRange(m, n); System.out.println(); } } private static void printPrimesInRange(int low, int hi) { // Print prime numbers in the range low...hi } }

Note that

 for (int num = j; num >= i ; num--) {

in addPrimeNumbers should be

 for (int num = j; num >= 1 ; num--) {

otherwise the result is not correct for ranges not starting at 1.

With respect to performance: Your function counts all divisors of a number, but

one can stop the test if any non-trivial divisor has been found,
any non-prime number \$ n \$ has a divisor which is \$ \le \sqrt n \$

Therefore this

 private static boolean isPrime(int n) { if (n < 2) { return false; } int limit = (int) Math.sqrt(n); for (int j = 2; j <= limit; j++) { if (n % j == 0) { return false; } } return true; } private static void printPrimesInRange(int low, int hi) { for (int n = low; n <= hi; ++n) { if (isPrime(n)) { System.out.println(n); } } }

would already improve the performance because the primality check for each number \$ n \$ is reduced from \$ O(n) \$ to \$ O(\sqrt n) \$.

For the range 100000 200000 this reduced the time from 43 seconds to approx 0.3 seconds on my 3.5 GHz Intel Core i5 iMac, measured with

 $ time java PrimeNumbers < input > output

and for the range 999900000 1000000000 I measured 0.7 seconds.

So this might be sufficiently fast to pass the challenge. For even better performance, use sieving methods like the (segmented) sieve of Eratosthenes (see for example https://www.geeksforgeeks.org/segmented-sieve/).

This is a great answer and well done. However I wonder if you tested the output. Specifically I think that isPrime() might wrongly identify 2 as not prime. Didn't test it, but that how it looks. I might be wrong. — markspace
– markspace, Commented Apr 29, 2018 at 15:14
@markspace: You are right, there was an error in the calculation of the upper limit for the divisor check. Apparently I did not inspect the (initial) output carefully enough. Thank you for the feedback! — Martin R
– Martin R, Commented Apr 29, 2018 at 15:22
@jackfield: Yes, it works with arbitrary many test cases. You can check the value of numTests if you want, but I don't find that necessary. — Martin R
– Martin R, Commented Apr 30, 2018 at 6:18

rossum · Accepted Answer · 2018-04-29 10:59:24Z

A prime number has only two factors, 1 and itself. However, counting factors -- as you do -- is not an efficient way to detect primes. A more efficient way is to look for factors in [2, n-1]. Any factor in that range indicates a composite number with three or more factors, so the search can be stopped at that point. As @Martin R pointed out, the search only need cover [2, sqrt(n)] to find the smaller of any pair of factors. In pseudocode this looks something like:

boolean isPrime(n) { for i in 2 to sqrt(n) do if (n MOD i == 0) return false // n is not prime, it has a third factor. endif endfor // n is prime if we get this far. return true }

There is a further efficiency with even numbers. If any even number is a factor of n, then 2 is also a factor. Hence, once you have tested for 2 as a factor, you don't need to check any other even numbers as a factor. This will roughly halve the runtime.

boolean isPrime(n) { // Even n if (n MOD 2 == 0) return n == 2 // 2 is the only even prime number. endif // Odd n for i in 3 to sqrt(n) step 2 do if (n MOD i == 0) return false // n has a third factor so it is not prime. endif endfor // n is an odd prime if we get this far. return true }

As a minor point, if you are going to check the given input parameters, it is probably better style to use a single checkParameters() method, given that the checks are so simple.

markspace · Accepted Answer · 2018-04-29 00:57:35Z

In case anyone is wondering, the following does NOT work. It takes too long at roughly the point shown in the code:

public class PrimeSieve { public static void main( String[] args ) { BigInteger num = BigInteger.ZERO; // BigInteger end = new BigInteger( "1000000000" ); BigInteger end = new BigInteger( "1000000" ); while( num.compareTo( end ) < 0 ) { num = num.nextProbablePrime(); } System.out.println( num ); } }

Output:

run: 1000003 BUILD SUCCESSFUL (total time: 8 seconds)

Stack Exchange Network

Outputting prime numbers in given ranges

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Outputting prime numbers in given ranges

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions