Skip to content

Instantly share code, notes, and snippets.

@nielsutrecht
Created June 18, 2014 09:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nielsutrecht/b8100450f23225b00094 to your computer and use it in GitHub Desktop.
Save nielsutrecht/b8100450f23225b00094 to your computer and use it in GitHub Desktop.
Sieve implementation in Java
public class Helper {
public static BitSet generatePrimes(final int maxNum) {
final BitSet set = new BitSet(maxNum+1);
set.clear(0, 1);
set.set(2, maxNum, true);
for (int i = 2; i < maxNum; i++) {
boolean isPrime = true;
for (int j = 0; j < (int) Math.sqrt(i); j++) {
if (!set.get(j)) {
continue;
}
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
int idx = i;
while (idx < maxNum + 1) {
idx += i;
set.set(idx, false);
}
}
}
return set;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment