Repository: TheAlgorithms/Java
Pull request #4217 (2023-06-20 16:23:49)

tests: add tests for `SieveOfEratosthenes`
This PR:
- adds tests for `SieveOfEratosthenes`, cf. 61a901f9e1fbb2d8f6705084322046605597ace5,
- updates `SieveOfEratosthenes.findPrimesTill` to throw an IllegalArgumentException for non-positive inputs, cf. a6072b8303bbe487594fef385a260a3bb579bd57,
- refactors `SieveOfEratosthenes.findPrimesTill`, cf. c4ba10442c33185ae591cf7da2c6c83ba893e57f,
- makes a _proper utility_ class out of `SieveOfEratosthenes`, cf. e193f849cde3f3dc8fb76a25b6a9f2dc608de559,
- updates doc-strs, cf. 22fd4e56319b807a3415e8e0ff313bb08cc47ab4.

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.



Patch:
diff --git a/src/main/java/com/thealgorithms/others/SieveOfEratosthenes.java b/src/main/java/com/thealgorithms/others/SieveOfEratosthenes.java
index ec014ecf..d7dcdbd1 100644
--- a/src/main/java/com/thealgorithms/others/SieveOfEratosthenes.java
+++ b/src/main/java/com/thealgorithms/others/SieveOfEratosthenes.java
@@ -3,55 +3,63 @@ package com.thealgorithms.others;
 import java.util.Arrays;
 
 /**
- * Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers
- * up to any given limit.
- *
- * @see <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Wiki</a>
+ * @brief utility class implementing <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
  */
-public class SieveOfEratosthenes {
+final public class SieveOfEratosthenes {
+    private SieveOfEratosthenes() {
+    }
 
-    /**
-     * Finds all prime numbers till n.
-     *
-     * @param n The number till which we have to check for primes. Should be more than 1.
-     * @return Array of all prime numbers between 0 to n.
-     */
-    public static int[] findPrimesTill(int n) {
-        Type[] numbers = new Type[n + 1];
-        Arrays.fill(numbers, Type.PRIME);
-        numbers[0] = numbers[1] = Type.NOT_PRIME;
+    private static void checkInput(int n) {
+        if (n <= 0) {
+            throw new IllegalArgumentException("n must be positive.");
+        }
+    }
+
+    private static Type[] sievePrimesTill(int n) {
+        checkInput(n);
+        Type[] isPrimeArray = new Type[n + 1];
+        Arrays.fill(isPrimeArray, Type.PRIME);
+        isPrimeArray[0] = isPrimeArray[1] = Type.NOT_PRIME;
 
         double cap = Math.sqrt(n);
         for (int i = 2; i <= cap; i++) {
-            if (numbers[i] == Type.PRIME) {
+            if (isPrimeArray[i] == Type.PRIME) {
                 for (int j = 2; i * j <= n; j++) {
-                    numbers[i * j] = Type.NOT_PRIME;
+                    isPrimeArray[i * j] = Type.NOT_PRIME;
                 }
             }
         }
+        return isPrimeArray;
+    }
 
-        int primesCount = (int) Arrays.stream(numbers).filter(element -> element == Type.PRIME).count();
-        int[] primes = new int[primesCount];
+    private static int countPrimes(Type[] isPrimeArray) {
+        return (int) Arrays.stream(isPrimeArray).filter(element -> element == Type.PRIME).count();
+    }
 
+    private static int[] extractPrimes(Type[] isPrimeArray) {
+        int numberOfPrimes = countPrimes(isPrimeArray);
+        int[] primes = new int[numberOfPrimes];
         int primeIndex = 0;
-        for (int i = 0; i < n + 1; i++) {
-            if (numbers[i] == Type.PRIME) {
-                primes[primeIndex++] = i;
+        for (int curNumber = 0; curNumber < isPrimeArray.length; ++curNumber) {
+            if (isPrimeArray[curNumber] == Type.PRIME) {
+                primes[primeIndex++] = curNumber;
             }
         }
-
         return primes;
     }
 
+    /**
+     * @brief finds all of the prime numbers up to the given upper (inclusive) limit
+     * @param n upper (inclusive) limit
+     * @exception IllegalArgumentException n is non-positive
+     * @return the array of all primes up to the given number (inclusive)
+     */
+    public static int[] findPrimesTill(int n) {
+        return extractPrimes(sievePrimesTill(n));
+    }
+
     private enum Type {
         PRIME,
         NOT_PRIME,
     }
-
-    public static void main(String[] args) {
-        int n = 100;
-        System.out.println("Searching for all primes from zero to " + n);
-        int[] primes = findPrimesTill(n);
-        System.out.println("Found: " + Arrays.toString(primes));
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/SieveOfEratosthenesTest.java b/src/test/java/com/thealgorithms/others/SieveOfEratosthenesTest.java
new file mode 100644
index 00000000..207c5146
--- /dev/null
+++ b/src/test/java/com/thealgorithms/others/SieveOfEratosthenesTest.java
@@ -0,0 +1,46 @@
+package com.thealgorithms.others;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.Test;
+
+class SieveOfEratosthenesTest {
+    @Test
+    public void testfFindPrimesTill1() {
+        assertArrayEquals(new int[] {}, SieveOfEratosthenes.findPrimesTill(1));
+    }
+
+    @Test
+    public void testfFindPrimesTill2() {
+        assertArrayEquals(new int[] {2}, SieveOfEratosthenes.findPrimesTill(2));
+    }
+
+    @Test
+    public void testfFindPrimesTill4() {
+        var primesTill4 = new int[] {2, 3};
+        assertArrayEquals(primesTill4, SieveOfEratosthenes.findPrimesTill(3));
+        assertArrayEquals(primesTill4, SieveOfEratosthenes.findPrimesTill(4));
+    }
+
+    @Test
+    public void testfFindPrimesTill40() {
+        var primesTill40 = new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
+        assertArrayEquals(primesTill40, SieveOfEratosthenes.findPrimesTill(37));
+        assertArrayEquals(primesTill40, SieveOfEratosthenes.findPrimesTill(38));
+        assertArrayEquals(primesTill40, SieveOfEratosthenes.findPrimesTill(39));
+        assertArrayEquals(primesTill40, SieveOfEratosthenes.findPrimesTill(40));
+    }
+
+    @Test
+    public void testfFindPrimesTill240() {
+        var primesTill240 = new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239};
+        assertArrayEquals(primesTill240, SieveOfEratosthenes.findPrimesTill(239));
+        assertArrayEquals(primesTill240, SieveOfEratosthenes.findPrimesTill(240));
+    }
+
+    @Test
+    public void testFindPrimesTillThrowsExceptionForNonPositiveInput() {
+        assertThrows(IllegalArgumentException.class, () -> SieveOfEratosthenes.findPrimesTill(0));
+    }
+}