Updated prime sieve

williamfiset · williamfiset · commit 32db7a969da5 · 2019-05-31T10:27:53.000-07:00
diff --git a/com/williamfiset/algorithms/math/CompressedPrimeSieve.java b/com/williamfiset/algorithms/math/CompressedPrimeSieve.java
@@ -7,11 +7,8 @@
  *
  * <p>Time Complexity: ~O(nloglogn)
  *
- * Compile:
- *   javac com/williamfiset/algorithms/math/CompressedPrimeSieve.java
- *
- * Run:
- *   java com/williamfiset/algorithms/math/CompressedPrimeSieve
+ * <p>Compile: javac com/williamfiset/algorithms/math/CompressedPrimeSieve.java
+ * <p>Run: java com/williamfiset/algorithms/math/CompressedPrimeSieve
  *
  * @author William Fiset, william.alexandre.fiset@gmail.com
  */
@@ -29,7 +26,7 @@ private static void setBit(long[] arr, int n) {
 
   // Returns true if the bit for n is off (meaning n is a prime).
   // Note: do use this method to access numbers outside your prime sieve range!
-  public static boolean isNotSet(long[] arr, int n) {
+  private static boolean isNotSet(long[] arr, int n) {
     if (n < 2) return false; // n is not prime
     if (n == 2) return true; // two is prime
     if ((n & 1) == 0) return false; // n is even
@@ -38,6 +35,11 @@ public static boolean isNotSet(long[] arr, int n) {
     return (chunk & mask) != mask;
   }
 
+  // Returns true/false depending on whether n is prime.
+  public static boolean isPrime(long[] sieve, int n) {
+    return isNotSet(sieve, n);
+  }
+
   // Returns an array of longs with each bit indicating whether a number
   // is prime or not. Use the isNotSet and setBit methods to toggle to bits for each number.
   public static long[] primeSieve(int limit) {
@@ -57,12 +59,14 @@ public static long[] primeSieve(int limit) {
     return chunks;
   }
 
+  /* Example usage. */
+
   public static void main(String[] args) {
     final int limit = 200;
-    long[] sieve = primeSieve(limit);
+    long[] sieve = CompressedPrimeSieve.primeSieve(limit);
 
-    for (int i = 1; i <= limit; i++) {
-      if (isNotSet(sieve, i)) {
+    for (int i = 0; i <= limit; i++) {
+      if (CompressedPrimeSieve.isPrime(sieve, i)) {
         System.out.printf("%d is prime!\n", i);
       }
     }
diff --git a/javatests/com/williamfiset/algorithms/datastructures/hashtable/HashTableDoubleHashingTest.java b/javatests/com/williamfiset/algorithms/datastructures/hashtable/HashTableDoubleHashingTest.java
@@ -2,7 +2,8 @@
 
 import static org.junit.Assert.*;
 
-import com.williamfiset.algorithms.datastructures.hashtable.DoubleHashingTestObject; // Move to test dir?
+import com.williamfiset.algorithms.datastructures.hashtable.DoubleHashingTestObject; // Move to test
+                                                                                     // dir?
 import com.williamfiset.algorithms.datastructures.hashtable.HashTableDoubleHashing;
 import java.util.*;
 import org.junit.*;
