# Prime numbers less than a given number N

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);
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...

• To get $\mathcal{O}(n \log n)$ time, you'll need to use a sieve. – Veedrac Jan 12 '15 at 11:36
• I'm pretty sure that if all you care about is the number of primes below N, it can be done in O(Sqrt(N) log(Sqrt(N)). – RBarryYoung Jan 12 '15 at 16:41

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.

• Right about now I'm feeling a bit idiot for overlooking the '<=' issue... of course it was that. Thanks! – Rodolfo Dias Jan 12 '15 at 8:32

The challenge states that N can be as large as 232-2. However, an int in Java is a signed 32-bit type, holding a maximum value of 231-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.