欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java 求质数

程序员文章站 2024-03-15 11:09:19
...

在找工作的时候,笔试中经常能碰到求素数的编程题,或者是求多少以内的素数,或者是求多少以内的素数和。

 

这两天,我也对这个问题有了点兴趣,上网找了一些资料。整理之后,得到以下两个方法,个人觉得第二种算是很优化的了。

 

第一种方法:

        for (int i = 1; i < mList.size(); i++) {
            int a = mList.get(i);
            
            for (int j = 0; j < i; j++) {
                int b = mList.get(j);
                
                if (a % b == 0) {
                    mList.remove(i);
                    i--;
                    break;
                }
            }
        }

这种方法是先把数字都存到一个集合当中,然后过滤掉2的倍数以及3的倍数,然后遍历下去,当遍历到一个数的时候,看看集合当中位置在它之前的数,有没有能整除的,如果有的话,在集合中删除掉这个数,以此类推。

 

这种方法基本就是根据质数的概念来计算的,在效率上要低一些。

 

 

第二种方法

 

这种方法类似的在网上有很多,关键点就在于求一个数是否是质数,就先求出它的平方根,之后判断是否能被平方根以内的除1以外的某个自然数整除,如果有能整除的,那么这个数即为合数,没有即为质数。

 

    @Override
    public void makePrimeList()
    {
        for (int i = 0; i < mList.size(); i++) {
            Integer dividend = mList.get(i);
            Integer divisor = 2;
            int sqrt = (int)Math.sqrt(dividend);
            
            for (int j = 0; j <= sqrt && divisor <= sqrt; j++) {
                divisor = mList.get(j);
                
                if (dividend % divisor == 0) {
                    mList.remove(dividend);
                    i --;
                    break;
                }
            }
        }
    }

 

说一下平方根强转的问题,其实不强转当然也可以,不过我测试了几次,感觉强转的话,可能会稍微快点。

 

在我写的这个算法当中,加入了分解质因数的概念,即只判断是否能够被平方根之前的某个质数整除,这样的话,效率提高了很多。

 

我粗略的统计了下,求十五万以内的质数,用第一种方法,在我的电脑上用时差不多为27秒左右的时间,而用第二种方法用时为16秒左右的时间,差不多快了十秒。

 

 

修改1:

刚刚在CSDN上看到了这个算法,同样算15万以内的质数的个数,测试了几次。平均用时30毫秒左右,再看看自己上面的代码,真是太惭愧了。

    @Override
    public void makePrimeList()
    {
        int n = mNumber;
        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++;
        }

        mList.clear();
        i = 2;
        while (i <= n) {
            if (b.get(i))
                mList.add(i);
            i++;
        }
    }