Prime numbers less than a given number N

Question

So, I began this challenge on CodeEval, which asks to print out the number of prime numbers less than any given integer N, where 0 < N < 4,294,967,295, ideally in O(N log N) time. I came up with this solution:

import java.io.*;
public class Main {
    public static void main (String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader buffer = new BufferedReader(new FileReader(file));
        String line;
        int limit;
        while ((line = buffer.readLine()) != null) {
            StringBuilder sb = new StringBuilder();
            line = line.trim();
            limit = Integer.valueOf(line);
            for (int i = 2; i <= limit; i++)
                if (isPrime(i) || i == 2)
                    sb.append(i + ",");
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb);
        }
    }

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

Basically, I'm building up a string where I append all prime numbers less than N (which is passed by argument). Testing it, it works perfectly (or so it seems); submitting it, I get a "partially" status and score of 85. Don't know really what I'm messing up here...

Answer 1

The challenge states

Print out the prime numbers less than a given number N

but you are iterating

for (int i = 2; i <= limit; i++)  

The ending condition should be i < limit.

• You need to check some edge cases:

  • limit == 0 here you would get an exception at sb.deleteCharAt(sb.length() - 1);
  • limit == 1 here you would get an exception at sb.deleteCharAt(sb.length() - 1);
  • limit == 2 using the ending condition mentioned above you would get an exception at at sb.deleteCharAt(sb.length() - 1); too

• If you start the loop (in main) at 3 and increment i by 2 this will be faster and you wouldn't need if (n % 2 == 0)

• Using braces {} for single if statements and loop bodies will make your code less errorprone.

• importing the whole java.io namespace is to much. Restrict the imports to the classes you need.

• the StringBuilder.append() method returns a StringBuilder object. So instead of calling sb.append(i + ",") you should call sb.append(i).append(",")

Refactoring

The while loop

while ((line = buffer.readLine()) != null) {
    StringBuilder sb = new StringBuilder();
    line = line.trim();
    limit = Integer.valueOf(line);
    if (limit > 2) {
         sb.append(2).append(",");
    }
    for (int i = 3; i < limit; i += 2){
        if (isPrime(i)){
            sb.append(i).append(",");
        }
    }
    if (sb.length() > 0) {
        sb.deleteCharAt(sb.length() - 1);
    }
    System.out.println(sb);
}

and the isPrime() method

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

in this way isPrime() would return true for each int n < 3 but this is for this case perfectly fine, because this is a private method which is only called in this specific szenario given strong borders.

Answer 2

The challenge states that N can be as large as 2³²-2. However, an int in Java is a signed 32-bit type, holding a maximum value of 2³¹-1. Therefore, your program is subject to overflow.

The simplest solution is to use long everywhere. In Java 8, you also have the option of using an int, but dutifully using methods such as Integer.parseUnsignedInt() and Integer.compareUnsigned() everywhere, so that the 32 bits are interpreted as unsigned. However, I don't see any reason to uglify your code just to save 32 bits, so I recommend using long.