package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/count-primes/
 */
public class Problem204 {
    public int countPrimes(int n) {
        // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
        int prime = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= n; i++) {
            set.add(i);
        }
        for (int i = 2; i <= n; i++) {
            if (!set.contains(i)) {
                continue;
            }
            for (int j = i; j <= n; j += i) {
                set.remove(j);
            }
            prime++;
        }
        return prime;
    }
    
    public static void main(String[] args) {
        Problem204 prob = new Problem204();
        System.out.println(prob.countPrimes(20));
        System.out.println(prob.countPrimes(999983));
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashSet;%0Aimport java.util.Set;%0A%0A
 /**%0A
@@ -125,24 +125,78 @@
 es(int n) %7B%0A
+        if (n %3C= 2) %7B%0A            return 0;%0A        %7D%0A
         // h
@@ -258,65 +258,41 @@
     
-int prime = 0;%0A        Set%3CInteger%3E set = new HashSet%3C%3E()
+boolean%5B%5D primes = new boolean%5Bn%5D
 ;%0A  
@@ -308,33 +308,32 @@
  (int i = 2; i %3C
-=
  n; i++) %7B%0A     
@@ -343,18 +343,24 @@
     
-set.add(i)
+primes%5Bi%5D = true
 ;%0A  
@@ -393,18 +393,21 @@
  = 2; i 
+* i 
 %3C
-=
  n; i++)
@@ -430,23 +430,17 @@
 f (!
-set.contains(i)
+primes%5Bi%5D
 ) %7B%0A
@@ -471,32 +471,82 @@
 ;%0A            %7D%0A
+            int k = i * i;%0A            int l = 0;%0A
             for 
@@ -558,26 +558,34 @@
 j = 
-i
+k
 ; j %3C
-=
  n; j 
-+
 =
+ k + (l *
  i)
+)
  %7B%0A 
@@ -603,21 +603,25 @@
     
-set.remove(j)
+primes%5Bj%5D = false
 ;%0A  
@@ -622,33 +622,40 @@
 se;%0A            
-%7D
+    l++;
 %0A            pri
@@ -655,16 +655,9 @@
     
-prime++;
+%7D
 %0A   
@@ -675,224 +675,162 @@
     
-return prime;%0A    %7D
+int result = 0;%0A        for (int i = 2; i %3C n; i++) %7B
 %0A    
-%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem204 prob = new Problem204();%0A        System.out.println(prob.countPrimes(20));%0A        System.out.println(prob.countPrimes(999983))
+    if (primes%5Bi%5D) %7B%0A                result++;%0A            %7D%0A        %7D%0A        return result
 ;%0A  

Solve problem 204