Findind质数--我的代码不能用 [关闭]。

Question

结束了。 这个问题需要 调试细节. 目前不接受回答。

---

想改进这个问题？ 请更新问题，使之成为 题外话 为Stack Overflow。

已关闭 上月.

改进这个问题

我有这段代码，我想用它来寻找质数。

public class Primzahlen {
    public static void main(String [] args) {
        for(int i = 1;i<100;i++) {
            for(int j=1;j<i;j++) {
                if(i%j == 0) {break;}
                if(j== (i-1)) {System.out.println(i);}  
            }           
        }
    }
}

但如果我试着运行程序，输出是空的。

Answer 1

你的代码的问题是这样的，。j 从1开始，每个数字都满足 i%j 断环 j 我推荐这段代码，它更有效，运行时间为O(sqrt(n))。

public class Primzahlen {
    public static void main(String [] args) {
        for(int i = 2;i<100;i++) {
            for(int j=2;  j < ((int)Math.sqrt(i))+2  ; j++) {
                if(i%j == 0) {break;}
                if(j== ((int)Math.sqrt(i))+1) {System.out.println(i);}
            }

        }
    }

}

Answer 2

以下是一些建议。

• 由于2是唯一的偶数素数，这使得后续的候选数只能是奇数。 所以从3开始，将候选数递增2。
• 只检查候选数的平方根以下的质数。
• 既然你是在找质数，那么就用已经找到的质数作为除数来检验质数。 假设候选数是17。 已经找到了2,3,5,7,11,13个质数。 通过应用前面的平方根法则，你需要做的就是看17是否被3或5整除，而不是被2到16整除。 如果它被任何大于其平方根的素数整除，那么它就已经被发现了。

对于一个完全不同的方法，请看 埃拉托斯泰尼的筛子.