[leedcode] Count Primes
3444 ワード
Description:
Count the number of prime numbers less than a non-negative number, n
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);
}
}*/