我正在编写一个程序来使用埃拉托色尼筛法算法(尽管有所不同)来查找素数。为了将所需字节数组的大小减半,我不表示任何偶数,而是坚持使用奇数(通过整数除以二来计算它们在数组中的位置)。
然而,我有一个问题。我的程序似乎没有将 17 或 113 识别为质数,尽管它们确实是质数。这是我的代码:
public class Eratosthes {
byte[] checklist;
int range;
public EratosthesConcurrent(int range) {
this.range = range/2;
this.checklist = new byte[this.range];
this.initAllChecked();
this.findPrimesSeq();
this.printPrimes();
}
private void initAllChecked(){
for(int i = 1; i < checklist.length; i++){
checklist[i] = 1;
}
}
private void crossOut(int i){
checklist[i/2] = 0;
}
private void findPrimesSeq(){
int curr = 3;
outer: while(curr < range*2){
for(int i = curr*curr; i < range*2; i+=2*curr){
if(i != curr && i%curr == 0){
if(i == 113){
System.out.println(curr);
}
crossOut(i);
}
}
secondLoop: for(int i = curr; i < range*2; i++){
if(checklist[i/2] == 1 && curr != i){
curr = i;
break secondLoop;
} else if(i == range*2-1 || i == range*2-2){ //Should be changed, might miss the last prime
break outer;
}
}
}
}
public void printPrimes(){
for(int i = 1; i < range; i++){
if(checklist[i] == 1){
System.out.println("Prime found: " + ((i*2)+1));
}
}
}
}
将以下内容添加到 crossOut 方法不会产生任何输出:
if(i == 17 || i == 113){
System.out.println("Found one of the numbers");
}
这对我来说很奇怪,因为程序的打印输出不包括 17 和 113,因此不检查它们的任何倍数。这给我留下了一个字节数组,其中检查了所有素数……以及 17 或 113 的任何倍数。
如果有人能在我的程序中发现错误,我将非常高兴——我自己已经调试了几个小时,但没有结果。提前致谢。
最佳答案
问题似乎是您没有检查除以 2。
您正在调用 crossOut(16)
在某些时候(特别是 4
的倍数),划掉了 17
的相应值.同样对于 112
导致 113
被划掉。
改变:
if (i != curr && i % curr == 0) {
到:
if (i % 2 != 0 && i != curr && i % curr == 0) {
并且这两个都被打印为素数。
另外,我有点担心这个循环到底在做什么——我没有太详细地查看输出,虽然它实际上看起来是所有素数,但我想你应该循环多个的 curr
, 第一个是 2*curr
(不是 curr*curr
),curr
之间的增量(不是 2*curr
),尽管我并不是说您所做的不正确,因为我需要更多时间来确切了解您的代码如何解决此问题。
关于java - Eratosthenes 筛法实现不检查某些数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22225218/