怎么求素数的个数?方法有多少种?

huangCF 发布于 2016/06/19 20:48
阅读 417
收藏 0
public static int count(){
int sum = 0;
int i = 0;
int y = 0;
for(i=101;i<=140;i++){
for( y=2;y<=i;y++){
if(i%y==0){
break;
}
}
if(i==y){
sum++;
}
}
return sum;

}

这段程序哪里有问题?

加载中
0
林中漫步
林中漫步

这个算法没问题,但效率低。 第二层循环不用从 2->i, 改为从2->i 的平方根即可。这样效率就从O(n),提升到O(log2N)。 如下:

public static int count() {
        int sum = 0;
        int i = 0;
        int y = 0;
        for (i = 101; i <= 140; i++) {
            int tmp = (int) Math.sqrt(i+1);
            for (y = 2; y <= tmp; y++) {
                if (i % y == 0) {
                    break;
                }
            }
            if (y > tmp) {
                sum++;
            }
        }
        return sum;
    }







0
燃灯
燃灯
看到这种格式,顿时觉得Python大法好。
Altman
Altman
当这段代码这个格式是python写的的时候,你会觉的还是括号大法好
h
huangCF
是是,问题还没解决呢兄弟
0
w
wenqiangzzh
看着没问题,貌似是对的呀
h
huangCF
求出来的个数不对
0
Shazi199
Shazi199

1.101

2.103

3.107

4.109

5.113

6.127

7.131

8.137

9.139

0
yangxd1986
yangxd1986

虽然从逻辑上看没什么问题,但是当区间比较大 区间下限比较高时 得到结果的时间太久了。

不如先准备一个字典,然后做个统计。

0
显峰哥
可以参考一下伪素数的算法原理,然后把伪素数的个数去掉,就是素数的个数了
返回顶部
顶部