Я реализовал алгоритм Сита для нахождения простых чисел до n. Я не могу узнать, почему он работает в бесконечном цикле.Почему моя реализация алгоритма Эратосфена запущена в бесконечный цикл?
Здесь я даю фрагмент кода. Пожалуйста помоги.
for(int j=2;j<=Math.sqrt(n);j++){
if(a[j]==true){
int x=0;
for(int p=(j*j+x*j); p<=n;x++){
a[p]=true;
}
}
}
Ваш внутренний цикл проверки р, но никогда не изменяя его
Некоторые оптимизаций предложения:
// When j is 2, the bitwise (2 & 1) will be 0, so the cycle increments by 1
// When j is odd (from 3 and above), the cycle goes in steps of 2
// (thus exploring only odd numbers)
// As a result, this cycle is twice as faster than the one progressing
// in increments of 1
// See here --------------------V
for(int j=2;j<=Math.sqrt(n);j+=(j & 1 ? 2 : 1)) {
if(a[j]==true){
// int x=0; // what for?
// a sum is cheaper than a multiplication
// Here --V and here --V
for(int p=j*j; p<=n;p+=j){
a[p]=true;
}
}
}
Когда вы это исправить, иметь в виду, что добавление дешевле, чем умножение и написать внутренний цикл как 'for (int p = j * j; p <= n; p + = j)'. –
Кроме того, не должно ли сито первое число, не помеченное как составное, и отметить все его кратность как составной? – biziclop
@biziclop «не должно сито брать первый номер, не помеченный как композитный», как вы думаете, что этого не происходит? (первый 'p', который не является составным, действительно' j * j' - любой ниже, чем был бы отмечен как составной, когда 'j' имел более низкие значения) –