[leedcode] Count Primes

3444 ワード

Description:
Count the number of prime numbers less than a non-negative number, n
public class Solution {
    public int countPrimes(int n) {
        if(n<3) return 0;
        int res=0;
        int temp[]=new int[n];
        
        int i;
        for(i=2;i<n-1;i++){
            temp[i++]=0;
            temp[i]=1;
        }
        temp[2]=1;
        for(i=3;i<n/2;i++){
            if(temp[i]==0) continue;
            if(temp[i]==1){
                for(int j=i+i;j<n;j=j+i){
                    temp[j]=0;
                }
            }
        }
        for(i=2;i<n;i++){
            if(temp[i]==1)
               res++;
        }
    
        return res;
    }
}
/*public class Solution {
    public int countPrimes(int n) {
        if(n<=2) return 0;
       // List primes=new ArrayList<Integer>(100);
        int primes []=new int[n];
        primes[0]=2;
        int res=1;
        //primes.add(2);
        int j;
        
        for(int i=3;i<n;i=i+2){
                //int flag=0;
                int s=(int)Math.sqrt(i);
            for( j=0;primes[j]<=s;j++){
              
                //int temp=(int)primes.get(j);
                if(i%primes[j]==0){
                   // flag=1;
                    break;
                }
                   
            }
             if(primes[j]>s) {
                 primes[res++]=i;
                 //++res;
               //primes.add(i);
               
            }
           
        }*/