Accepted code using seiveoferatosthenes,any improving?


  • 0
    L

    public class Solution {

    public int countPrimes(int n) {
    	boolean[] flags = sieveOfEratosthenes(n);
    	int count = 0;
    	for(int i=0;i<flags.length;i++)
    	{
    		if(flags[i])
    		{
    			count ++ ;
    		}
    	}
    	return count;
    }
    public boolean[] sieveOfEratosthenes(int n)
    {
    	boolean[] flags = new boolean[n];
    	//int count = 0;
    	for(int i=2;i<flags.length;i++)
    	{
    		flags[i] = true;
    	}
    	int prime = 2;
    	while(prime<=Math.sqrt(n))
    	{
    		crossOff(flags,prime);
    		
    		prime = getNextPrime(flags,prime);
    		
    		if(prime >= flags.length)
    		{
    			break;
    		}
    	}
    	return flags;
    	
    }
    public void crossOff(boolean[] flags,int prime)
    {
    	for(int i=prime*prime;i<flags.length;i+=prime)
    	{
    		flags[i] = false;
    	}
    }
    
    public int getNextPrime(boolean[] flags,int prime)
    {
    	int next = prime + 1;
    	while(next < flags.length&&!flags[next])
    	{
    		next ++ ;
    	}
    	return next;
    }
    

    }


Log in to reply
 

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