My Java 256ms solution, can it be faster?


  • 0
    E
    public class Solution {
    public int countPrimes(int n) {
                boolean bool[] = new boolean[n];
                                int counter = 0;
                                int j = 0;
    
                                for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
                                                j = i + i;
                                                if (!bool[i]) {
                                                                while (j < n) {
                                                                            
                                                                             if (!bool[j])   bool[j] = true;
                                                                                j = j + i;
                                                                }
                                                }
                                }
    
                                for (int i = 2; i < bool.length; i++) {
                                                if (!bool[i]) {
                                                                counter++;
                                                }
                                                
    
                                }
                                
                                return counter;
    
    }
    

    }


  • 0
    E

    Little better

    public class Solution {
    public int countPrimes(int n) {
                boolean bool[] = new boolean[n];
                                if (n <= 2) return 0;
                                int counter = n-2;
                                int j = 0;
    
                                for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
                                                j = i + i;
                                                if (!bool[i]) {
                                                                while (j < n) {
                                                                            
                                                                             if (!bool[j]) {
                                                                                 bool[j] = true;
                                                                                 counter --;
                                                                             }
                                                                                j = j + i;
                                                                }
                                                }
                                }
    
                                
                                
                                return counter;
    
    }
    

    }


  • 0
    Z

    Logic is clear, but how to prove that all composite numbers less than n^2 could be represented by the product of multiple prime numbers less than or equal to n.


  • 0
    V

    what's the logic or algorithm over here.


Log in to reply
 

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