美文网首页自误自乐玩算法
素数Eratosthenes筛子算法之Java实现

素数Eratosthenes筛子算法之Java实现

作者: DataNerd | 来源:发表于2017-09-26 03:49 被阅读0次

    昨天自己看《Java核心技术》的时候看到了这种实现查找素数的算法,决定把它记录下来。
    Eratosthenes筛子算法的思想是如果一个数是素数的倍数,则这个数不是素数。
    实现源码如下:

    import java.util.*;
    
    public class Sieve{
        public static void main(String[] args){
            int n = 5;
            BitSet b = new BitSet(n + 1);
            int count = 0;
            
            int i;
            for(i = 2;i <= n;i ++){
                b.set(i);
            }
            i = 2;
            while(i * i <= n){
                if(b.get(i)){
                    count ++;
                    int k = 2 * i;
                    while(k <= n){
                        b.clear(k);
                        k += i;
                    }
                }
                i ++;
            }
    
            while(i <= n){
                if(b.get(i))
                    count ++;
                i ++;
            }
    
            System.out.println("count " + count);
        }
    }
    

    相关文章

      网友评论

        本文标题:素数Eratosthenes筛子算法之Java实现

        本文链接:https://www.haomeiwen.com/subject/fuvjextx.html