Сито реализации Эратосфена не проверяет определенные числа
Я пишу программу для поиска простых чисел, используя хорошее старое сито алгоритма Эратосфена (хотя и с изюминкой). Для того, чтобы вдвое уменьшить размер необходимого массива байтов, я не представляю никаких четных чисел, а придерживаюсь нечетных (вычисляя их положение в массиве целочисленным делением на два).
Однако у меня есть одна проблема. Моя программа, кажется, не распознает 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));
}
}
}
}
Добавление следующий способ изменения не производить никаких выходных данных:
if(i == 17 || i == 113){
System.out.println("Found one of the numbers");
}
И это очень странно для меня, потому что распечатка из программы исключает 17 и 113, и таким образом не проверяет ни один из их кратных. Это оставляет меня с массивом байтов, где проверяются все простые числа... а также любой кратный 17 или 113.
Я был бы очень рад, если бы кто-нибудь нашел ошибку в моей программе-я сам отлаживал ее часами, безрезультатно. Заранее спасибо.2 ответа:
Проблема, похоже, в том, что вы не проверяете деление на 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
), хотя я не говорю, что вы сделали неправильно, так как мне нужно немного больше времени, чтобы понять, как именно ваш код решает эту проблему.
for(int i = curr*curr; i < range*2; i+=2*curr){
Первое значение = 9, затем переходит в 15
Карр = 3 - 3*3 = 9
I += 2 * curr = 9 + 6
Псевдо:
outerNum = sqrt[range] array[boolean] size of range array[0 & 1] = false for i = 2 to outernum for j = i to range if j % i != 0 array[j] = false for i = array[boolean] length print if array[i] = true
Это из памяти, так что простите, если какие-то ошибки.