首页 > 其他 > 详细

Count Primes

时间:2015-05-05 21:09:01      阅读:127      评论:0      收藏:0      [点我收藏+]

https://leetcode.com/problems/count-primes/

Description:

Count the number of prime numbers less than a non-negative number, n

click to show more hints.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

 1 import java.util.BitSet;
 2 
 3 public class Solution {
 4     public static int countPrimes(int n) {
 5         BitSet bs = new BitSet(n);
 6         bs.set(0); bs.set(1);
 7         int ind = 0, count = 0;
 8         while(ind < n){
 9             ind = bs.nextClearBit(ind + 1);
10             if(ind >= n)
11                 return count;
12             count++;
13             for(long i = (long)ind* (long)ind; i < n; i += ind)
14                 bs.set((int)i);
15         }
16         return count;
17     }
18 
19     public static void main(String[]args){
20     
21     System.out.println(countPrimes(1500000));
22     }
23 }

 

Count Primes

原文:http://www.cnblogs.com/qq1029579233/p/4479936.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!