# Comparing 2 distinct sieve of Eratosthenes algorithms in Java

In this post, I will present and compare two distinct algorithms for sieve of Eratosthenes:

`com.github.coderodde.math.prime.PrimeFinder`

``````package com.github.coderodde.math.prime;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

/**
* This abstract defines the API for finding prime numbers.
*
* @author Rodin "rodde" Efremov
* @version 1.6 (Sep 12, 2021)
* @since 1.6 (Sep 12, 2021)
*/
public abstract class PrimeFinder {

/**
* Finds all the primes no larger than {@code limit} and returns them in a
* sorted list.
*
* @param limit the maximum allowed prime.
* @return a list of primes.
*/
public abstract BitSet findPrimesUpTo(int limit);

/**
* Converts all the primes in {@code bitSet} to the list.
*
* @param bitSet the target bit set describing the primes.
* @param numberOfBits the number of actual numbers in {@code bitSet}.
* @return the prime list.
*/
public static List<Integer>
primeBitSetToList(
BitSet bitSet,
int numberOfBits) {

List<Integer> list = new ArrayList<>(bitSet.size());

for (int i = 0; i < bitSet.size(); i++) {
if (bitSet.get(i)) {
}
}

return list;
}

protected void checkLimit(int limit) {
if (limit < 0) {
throw new IllegalArgumentException("Negative limit: " + limit);
}
}
}
``````

`com.github.coderodde.math.prime.impl.LinearithmicPrimeFinder`

``````package com.github.coderodde.math.prime.impl;

import com.github.coderodde.math.prime.PrimeFinder;
import java.util.BitSet;

/**
* This class implements the basic sieve of Eratosthenes running in
* {@code O(n log n)} time.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Sep 12, 2021)
* @since 1.6 (Sep 12, 2021)
*/
public final class LinearithmicPrimeFinder extends PrimeFinder {

/**
* {@inheritDoc }
*/
@Override
public BitSet findPrimesUpTo(int limit) {
checkLimit(limit);

if (limit < 2) {
return new BitSet(limit);
}

if (limit == 2) {
BitSet bitSet = new BitSet(3);
bitSet.set(2);
return bitSet;
}

BitSet bitSet = new BitSet(limit + 1);
bitSet.set(0, bitSet.size(), true);
bitSet.clear(0);
bitSet.clear(1);

// Deal with powers of two:
for (int i = 4; i <= limit; i += 2) {
bitSet.set(i, false);
}

// Deal with powers of odd primes:
for (int primeCandidate = 3;
primeCandidate <= limit;
primeCandidate += 2) {
if (bitSet.get(primeCandidate)) {
for (int i = 2 * primeCandidate;
i <= limit;
i += primeCandidate) {
bitSet.set(i, false);
}
}
}

return bitSet;
}
}
``````

`com.github.coderodde.math.prime.impl.FasterPrimeFinder`

``````package com.github.coderodde.math.prime.impl;

import com.github.coderodde.math.prime.PrimeFinder;
import java.util.BitSet;

/**
* This class implements a sieve of Eratosthenes prime finder described in
* <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode">
* Wikipedia</a>. Runs in {@code O(n log log n)} time.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Sep 12, 2021)
* @since 1.6 (Sep 12, 2021)
*/
public final class FasterPrimeFinder extends PrimeFinder {

@Override
public BitSet findPrimesUpTo(int limit) {
checkLimit(limit);

if (limit < 2) {
return new BitSet(limit);
}

if (limit == 2) {
BitSet bitSet = new BitSet(3);
bitSet.set(2);
return bitSet;
}

BitSet bitSet = new BitSet(limit + 1);
bitSet.set(0, bitSet.size(), true);
bitSet.clear(0);
bitSet.clear(1);

for (int i = 2, end = (int)(Math.sqrt(limit)) + 1; i < end; i++) {
if (bitSet.get(i)) {
for (int j = i * i; j <= limit; j += i) {
bitSet.clear(j);
}
}
}

return bitSet;
}
}

``````

`com.github.coderodde.math.prime.Demo`

``````package com.github.coderodde.math.prime;

import com.github.coderodde.math.prime.impl.FasterPrimeFinder;
import com.github.coderodde.math.prime.impl.LinearithmicPrimeFinder;
import java.util.BitSet;
import java.util.List;

public final class Demo {

private static final int MAX_PRIME = 300_000_000;

public static void main(String() args) {
PrimeFinder primeFinder1 = new LinearithmicPrimeFinder();
PrimeFinder primeFinder2 = new FasterPrimeFinder();

List<Integer> list1 = getPrimeList(MAX_PRIME, primeFinder1);
List<Integer> list2 = getPrimeList(MAX_PRIME, primeFinder2);

System.out.println("Agreed: " + list1.equals(list2));
}

private static List<Integer> getPrimeList(int limit, PrimeFinder finder) {
long startTime = System.currentTimeMillis();

BitSet primeSieve = finder.findPrimesUpTo(limit);

long endTime = System.currentTimeMillis();
long duration = endTime - startTime;

System.out.println(
finder.getClass().getSimpleName() + " in " + duration +
" milliseconds.");

List<Integer> list =
PrimeFinder.primeBitSetToList(primeSieve, limit + 1);

return list;
}
}
``````

Critique request

Please, tell me anything that comes to mind. Especially, I am concerned with class and method naming.