Legendre prime counting function: Difference between revisions

Content deleted Content added

Inline

@@ Line 360: / Line 360: @@
     private List<Integer> primes;
-    private Map<Integer, Map<Integer, Integer>> phiCache = new HashMap<>();
     public LegendrePrimeCounter(int limit) {
@@ Line 376: / Line 375: @@
         if (a == 0)
             return x;
+        if (a == 1)
-        Map<Integer, Integer> map = phiCache.computeIfAbsent(x, k -> new HashMap<>());
-        Integer value = map.get(a);
+            return x - (x >> 1);
-        if (value != null)
+        int pa = primes.get(a - 1);
-            return value;
+        if (x <= pa)
-        int result = phi(x, a - 1) - phi(x / primes.get(a - 1), a - 1);
+            return 1;
-        map.put(a, result);
+        return phi(x, a - 1) - phi(x / primes.get(a - 1), a - 1);
-        return result;
     }