# Efficient way to calculate the sum of all primes between a range

Problem

I'm trying to write a code in which Q questions are asked and each question contains two numbers A and B. For each question, I have to find the sum of all primes between integers A and B (inclusive). I've written a program that works, but it isn't fast enough to pass all the restrictions. Is there any way to improve the efficiency of my code?

Restrictions

1≤Q≤10^5

1≤A≤B≤10^5

Time limit: 0.6s

import java.io.*;
import java.util.*;

public class sumofprimes{
static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static StringTokenizer st;
static boolean isPrime(int n){
if(n==1)return false;
for (int i=2; i*i<=n; i++)
if (n%i==0) return false;
return true;
}

static int sum(int a, int b){
int sum=0;
for(int i=b; i>=a; i--) {
boolean prime=isPrime(i);
if(prime) sum+=i;
}
return sum;
}
public static void main(String[] args)throws IOException{
for(int i=0; i<q; i++){
System.out.println(sum(a,b));
}
}
static String next () throws IOException {
while (st == null || !st.hasMoreTokens())
return st.nextToken();
}
static int readInt () throws IOException {
return Integer.parseInt(next());
}
}

• In terms of really efficient. There’s no doubt in my mind that there are deep mathematical results you could use to compute the sum of primes directly. But for something more efficient then what you have I would suggest just precomputing all the primes up to 10^5 e.g. a typical prime sieve. If you like you could also precompute the partial sums. – Countingstuff Oct 14 at 1:13
• @Countingstuff I am afraid there are no math results you have in mind; some asymptotics perhaps. That said, you are absolutely right re preprocessing with a sieve and partial sums. – vnp Oct 14 at 1:51
• Where is this problem from? – superb rain Oct 15 at 23:03
• @vnp mathoverflow.net/questions/81443/… proposes something along the lines of what I had in mind, I don't really follow the marked answer but Johan Andersson's idea makes sense. Unfortunately it's the same complexity as using the best (albeit highly impractical) sieve I know, O(n^(0.5 + o(1)), so I guess you're right. – Countingstuff Oct 16 at 1:06

Nice implementation, it's already efficient but as noted in the comments can be improved. Few general suggestions:

• Format the code: many IDE support auto formatting or you can use an online formatter.

• Omitting brackets is not good practice: it's better to include the brackets to avoid confusion when reading or changing the code. See the difference from:

static boolean isPrime(int n){
if(n==1)return false;
for (int i=2; i*i<=n; i++)
if (n%i==0) return false;
return true;
}


To:

static boolean isPrime(int n) {
if (n == 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

• Arrange the methods from general to specific, it's easier to follow. From:

static boolean isPrime(int n){
}

static int sum(int a, int b){
//call isPrime
}

public static void main(String[] args)throws IOException{
// call sum
}

static String next () throws IOException {
}

static int readInt () throws IOException {
// call next
}


To:

public static void main(String[] args)throws IOException{
// call sum
}

static int readInt () throws IOException {
// call next
}

static String next () throws IOException {
}

static int sum(int a, int b){
//call isPrime
}

static boolean isPrime(int n){
}

• The methods readInt and next can be replaced with java.util.Scanner:

Scanner scanner = new Scanner(System.in);
int q = scanner.nextInt();

• Close the resources: br.close() (or scanner.close()) at the end of main or if exceptions occur.

• PrintWriter pr is not used.

• The method sum(int a, int b) does not sum two integers. A better name might be sumPrimesBetween

• StringTokenizer is discouraged for new code, from the docs:

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

## Performance

As mentioned in the comments, since you know the upper bound 10^5 you can precompute all the prime numbers in advance. The main logic can be:

1. Precompute all prime numbers until 10^5: you can use an array of boolean initialized to true and then set the corresponding index to false if not prime. For example:
static void computePrimesUntil(int n) {
isPrime = new boolean[n+1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i] && (long) i * i <= n) {
for (int j = i * i; j <= n; j += i){
isPrime[j] = false;
}
}
}
}


Code inspired from here.

1. Parse all the questions from the user
2. Output the sum of primes for each question

Note: depending on how the total running time is calculated, you need to consider the time to parse the input and print the results. The total running time also depends on the machine where you run the program.

• No idea why you say "it's already efficient". It's absolutely not. Not even yours is, although it's a lot better. – superb rain Oct 14 at 10:28
• Honestly, I've seen worse implementations of isPrime, at least OP uses the condition i*i<=n. Definitely there are more efficient solutions, my suggestion is for OP's problem. Feel free to post yours. – Marc Oct 14 at 11:37
• Sure. An inefficient isPrime would make it three or four levels of inefficient rather than two or three. But two or three levels of inefficient are still not "efficient". I might've written one if the OP hadn't kept the source of the problem secret. Can't be bothered to write my own test suite if the OP can't be bothered to provide a link to where I get the actual test suite already ready for use. – superb rain Oct 14 at 11:51
• @superbrain The question is from DMOJ and the link is dmoj.ca/problem/alexquiz2. – PencilKnot Oct 16 at 0:39
• @PencilKnot Doesn't work for me, shows "No such problem". – superb rain Oct 16 at 0:44

In this answer, you are told that you can precompute the list of primes. But if space is not a concern, we can go further and precalculate the sums.

Assuming we have an array prime such that prime[x] tells us if x is prime or not.

long[] primeSumUpTo = new long[prime.length];

// this explicit initialization is not necessary as 0 is the default value
primeSumUpTo[0] = 0;
for (int i = 1; i < prime.length; i++) {
primeSumUpTo[i] = primeSupUpTo[i - 1];
if (prime[i]) {
primeSumUpTo[i] += i;
}
}


Now if we want to know the sum of primes between a and b inclusive, we can just do a simple calculation.

long primeSumBetween = primeSumUpTo[b] - primeSumUpTo[a - 1];


Your original algorithm was $$\\mathcal{O}(qn^{1.5})\$$ where $$\q\$$ is the number of questions and $$\n\$$ is the size of the range. The revised form in the other answer is $$\\mathcal{O}(qn + n \log \log n)\$$, which is somewhat better. But this version would be $$\\mathcal{O}(q + n \log \log n)\$$. Note that if $$\q\$$ and $$\n\$$ are equal as in the worst case from the problem, this gives powers of 2.5, 2, and more than 1 but less than 2 respectively.

Note that the actual questions may use a smaller range than $$\n\$$. That could cause a timing fail because this version always sums the full $$\n\$$. We can avoid this by reading all the questions first (using more memory again) and then limiting our sums to the actual limits. In pseudocode, from min(a) - 1 to max(b).

• Now we just need to use an O(n) sieve so you can replace the clunky "more than 1 but less than 2" with just "1" :-) – superb rain Oct 18 at 18:46

Style Guide

• always use braces when using a loop or if-statements.
• make spaces between operators.
• Don't use *-imports.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class SumOfPrimes {
private static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
private static StringTokenizer st;

public static void main(String[] args) throws IOException {
for(int i = 0; i < q; i++) {
System.out.println(sum(a, b));
}
}

private static boolean isPrime(int n) {
if(n == 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static int sum(int a, int b) {
int sum = 0;
for(int i = b; i >= a; i--) {
boolean prime = isPrime(i);
if(prime) {
sum += i;
}
}
return sum;
}

private static String next () throws IOException {
while (st == null || !st.hasMoreTokens()) {
}
return st.nextToken();
}

static int readInt () throws IOException {
return Integer.parseInt(next());
}
}


Tell the user what to do

When I first started the program, I didn't know what to do, because the program didn't tell me:

public static void main(String[] args) throws IOException {
System.out.println("How many calculations do you want to make?");
for(int i = 0; i < q; i++) {
System.out.println("Enter the lower bound:");
System.out.println("Enter the upper bound:");
System.out.println("Result:");
System.out.println(sum(a, b));
}
}


Input validation

Your program crashes when the user enters a string instead of a number. You can avoid that by using a function like the following instead of next() and readInt():

private static int getUserInput(String var) {
Scanner sc = new Scanner(System.in);
int number;
while(true) {
try {
System.out.print(var);
number = sc.nextInt();
if(number < 0) {
throw new InputMismatchException();
}
return number;
}
catch(InputMismatchException e) {
System.out.println("Enter a number >= 0.");
sc.nextLine();
}
}
}


lower bound > upper bound

You should check if the user enters a and b so that a > b:

public static void main(String[] args) throws IOException {
int q = getUserInput("How many calculations do you want to make?");
for(int i = 0; i < q; i++) {
int a = getUserInput("Enter the lower bound:");
int b = getUserInput("Enter the upper bound:");

if(a > b) {
int c = a;
a = b;
b = c;
}
System.out.println("Result:");
System.out.println(sum(a, b));
}
}


Code

import java.util.Scanner;
import java.io.IOException;
import java.util.InputMismatchException;

public class SumOfPrimes {

public static void main(String[] args) {
int q = getUserInput("How many calculations do you want to make?");
for(int i = 0; i < q; i++) {
int a = getUserInput("Enter the lower bound:");
int b = getUserInput("Enter the upper bound:");

if(a > b) {
int c = a;
a = b;
b = c;
}
System.out.println("Result:");
System.out.println(sum(a, b));
}
}

private static boolean isPrime(int n) {
if(n == 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static int sum(int a, int b) {
int sum = 0;
for(int i = b; i >= a; i--) {
boolean prime = isPrime(i);
if(prime) {
sum += i;
}
}
return sum;
}

private static int getUserInput(String var) {
Scanner sc = new Scanner(System.in);
int number;
while(true) {
try {
System.out.print(var);
number = sc.nextInt();
if(number < 0) {
throw new InputMismatchException();
}
return number;
}
catch(InputMismatchException e) {
System.out.println("Enter a number >= 0.");
sc.nextLine();
}
}
}
}

• Those prints will likely make it wrong, though. Meaning it'll get judged "Wrong Answer" because its output doesn't match the expected output. Interesting dilemma, I don't know whether I ever thought about it: How to make it work in both cases. My best idea is to try reading the first input with a timeout. If there's input within let's say 0.1 seconds, assume it's from the judge system or some other program (or a fast user who knows what they're doing). Otherwise, assume it's manual input by a human and show those instructions. – superb rain Oct 15 at 22:20
• @superbrain Are you talking about possible unit tests here? If that is the case, you can just use the sum()-method directly and you will not have to think about outputs, just about returns. – Philipp Wilhelm Oct 15 at 22:54
• To me it rather looks like one of those sites where the judge feeds the input via stdin and takes the output via stdout, not directly using any method. – superb rain Oct 15 at 23:00
• @superbrain Ah ok. I didn't notice that. Thanks for the hint. – Philipp Wilhelm Oct 16 at 2:40