291 ms java solution


  • 1
    A
    	if (n < 3)
    		return 0;
    	int a[] = new int[n - 1];
    	for (int i = 0, j = 2; i < n - 2; i++, j++) {
    		a[i] = j;
    	}
    	boolean found = true;
    	int nonZeroIndex = 0;
    	int sqrt =(int) Math.sqrt(n);
    	while (found) {
    		found = false;
    		nonZeroIndex = findFirstNumber(a, nonZeroIndex);
    		if (nonZeroIndex == -100) {
    			break;
    		}
    		int j = a[nonZeroIndex];
    		int k = nonZeroIndex + j;
    		if (j > sqrt){
    			break;
    		}
    		for (; k < a.length;) {
    			if (a[k] % j == 0) {
    				a[k] = 0;
    				found = true;
    			}
    
    			k += j;
    		}
    		nonZeroIndex++;
    	}
    	int count = 0;
    	for (int g = 0; g < a.length; g++) {
    		if (a[g] != 0)
    			count++;
    	}
    	return count;

Log in to reply
 

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