My Java code(remove all even number , just select in odd numbers)


  • 0
    Z

    /**
    *因为所有的偶数都不是质数,所以只需要在奇数里面去取质数即可,而且所有质数的奇数倍都不是质数,所以
    *当找到一个质数时把所有质数的奇数倍都筛选掉,这样找的数就是所有的质数
    */
    public class Solution {
    public int countPrimes(int n) {
    if (n < 3)
    return 0;

    	int OddNums = n / 2;
    	int sum=0;
    	boolean[] primes = new boolean[OddNums];
    	//将所有的奇数都设置成true,2n+3
    	for (int i = 0; i < OddNums; i++)
    		primes[i] = true;
    	
    	
    	for(int i=0;i<OddNums;i++)
    	{
    		int tmpOddNum=2*i+3;
    		if(primes[i])
    		{
    			int indexPrime;
    			for(int j=1;(2*j+1)*tmpOddNum<n;j++)
    			{
    				indexPrime=((2*j+1)*tmpOddNum-3)/2;
    				primes[indexPrime]=false;
    			}
    		}
    	}
    	for(int i=0;i<OddNums;i++)
    		if(primes[i])
    			sum++;
    	
    	return sum;
    }
    

    }


  • 0
    S

    One trivial bug. 1 is not a prime number. Incorrect output after running your solution.


Log in to reply
 

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