I have made an array boolean prime[] to generate all the prime numbers between 1 to N. Initially the length of array is N+1. when I execute the for loop with condition for(int i=2; i*i<=N;i++) the value of c(total prime numbers) < N but with condition for(int i=2; i<=N;i++) the value of c(total prime numbers) > N .How's that possible?

public int exactly3Divisors(int N)
    {
        int n = N;
        boolean prime[] = new boolean[n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 

        for(int p = 2; p*p <=n; p++) 
        { 
            // If prime[p] is not changed, then it is a prime 
            if(prime[p] == true) 
            { 
                // Update all multiples of p 
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 


        int num=0;
        int c=0;
        System.out.println("Length "+ prime.length);

        for(int i=2; i<=N;i++){ //if we change i<=N with i*i<=N works fine

            if(prime[i]==true)
             c++;
           if(prime[i]==true && i*i <=N){
                 num++;
        //     System.out.print(i+"-"+(i*i)+" ");
           }

        }
        System.out.print("c = "+c) ; 
        return num;
    }

The value of c expected must be < N but it actually way larger than N

0 Answers