204. Count Primes By Prabu Mohan


  • 0
    P

    '''
    import java.util.Scanner;
    import java.util.BitSet;

    class Solution {

    public static void main (String args[]){
        
       int n = new Scanner(System.in).nextInt();
       
            System.out.println(countPrimes(n));
        
    }
    public static int countPrimes(int n) {
       int output;
        
        if (n == 0 || n == 1 || n == 2) 
                return 0;
        else if (n ==3)
       return 1;
            BitSet set = new BitSet();
        n = n - 1;
        int sqRt = (int) Math.sqrt(n);
        int count = n;
        for (int i = 2; i <= sqRt; i++) {
            if (!set.get(i)) {
                for (int j = 2; (i * j) <= n; j++) {
                    if (!set.get(i * j)) {
                        count--;
                        set.set(i * j);
                    }
                }
            }
        }
        return count - 1;
    }
    

    }

    '''


Log in to reply
 

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