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++;
}
}
上一篇: Java实现求100以内的质数
下一篇: Docker中两个容器之间实现数据共享