public static void main(String[] args) {
        Watch.start();
        List<Integer> primes = Utils.sievePrimes(N);
        HashSet<Integer> primesSet = new HashSet<>(primes);
        int[] divisors = new int[N];
        for (int n = 2; n < N; n++) {
            if (primesSet.contains(n)) {
                divisors[n] = 2;
            } else {
                int t = n;
                int count = 1;
                for (int i = 0; ; i++) {
                    int prime = primes.get(i);
                    if (prime * prime > t) {
                        count *= 2;
                        break;
                    }
                    int exponent = 1;
                    while (t % prime == 0) {
                        exponent++;
                        t /= prime;
                    }
                    if (exponent > 1) count *= exponent;
                    if (t == 1) break;
                }
                divisors[n] = count;
            }
        }
        int count = 0;
        for(int n = 2; n < N - 1; n++){
           if(divisors[n] == divisors[n + 1]){
               count++;
           }
        }
        System.out.println(count);
        Watch.stop();
    }