What is the time complexity of this java solution?


  • 0
    L
    public class Solution {
    public int countPrimes(int n) {
    	if(n<=1) return 0;
    	int curr = 2;
    	int count=0;
    	boolean flag[] = new boolean[n];
    	for(int i=2; i<n; i++){
    		flag[i]= true;
    	}
    	while(curr*curr <=n){
    		for(int i=curr*curr,j=0; (i+j*curr)<n; j++){
    			flag[i+j*curr]=false;
    		}
    		for(int i = curr+1 ; i<n; i++){
    			if(flag[i]==true){
    				curr = i;
    				break;
    			}
    		}
    	}
    	for(int i=1;i<n;i++){
    		if(flag[i])count++;
    	}
    	return count;
    }
    

    }


Log in to reply
 

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