204. Count Primes question


  • 0
    J

    Here is my solution to the Count Primes question

      public class Solution {
            public int countPrimes(int n) {
                boolean[] isPrime = new boolean[n];
                for (int i = 0; i < n; i ++) {
                    isPrime[i] = true;
                }
            
                for (int i = 2; i * i < n; i ++) {
                    if (isPrime[i]) {
                        System.out.println(i*i);
                        for (int j = i; i * j < n; j++) {
                            isPrime[i * j] = false;
                        }
                    }
                }
                int count = 0;
                for (int k = 2; k < n; k ++) {
                    if (isPrime[k]) count++;
                }
                return count;
                
            }
        }
    

    I am wondering why do i need the "i*i < n" condition in the second loop? If I only use "i < n", the following "isPrime[i]" should be still in the correct bound, but it throws "java.lang.ArrayIndexOutOfBoundsException: -2146737495".

    I guess it is because i is too large in this case so i * j becomes a negative number. However, shouldn't "i * i" also become negative in this case? Then why the code above still works?


  • 0
    D

    Probably it becomes negative after the first iteration, like ii is fine, i(i+k) out of bounds.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.