Туплю в решении вроде бы простой задачи?

Question

[Roma789]

function g(n) {
  let b = 0;
  for(let i = 2; i <= n; i++){
    for (let j = 2; j < i; j++) {
      if (i % j !== 0){
        b+=1
      }
    }
  }
  console.log(b);
};
g(10)

Привет,вот функция подсчёта количества простых чисел,вроде всё правильно,но почему то счётчик набирает гораздо большее простые числа в промежутке от 2 до n чем на самом деле,например от 2 до 10 28 простых чисел,где я ошибся?

Answer 1

[Олег]

i % j !== 0

Как я понимаю Вы решаете задачу нахождения количества простых чисел меньше или равных заданному.
Сделал вывод по внешнему циклу i
Дальше вы пытаетесь проверить что i простое.
ну во первых j идти до i-1 не нужно - верхняя граница квадратный корень из i
во вторых цикл надо прерывать при остатке от деления равному нолю
и только если после прохода цикла не было сработки - число простое.

в общем как я писал сразу ошибка в логике проверки что число простое.
Простое число - нет ни одного делителя кроме 1 и N
т.е. цикл должен пробежать целиком и флаг остался истиной

Comments

[Roma789]

не совсем понял,что не так в условии

[ThunderCat]

Roma789, ну, тогда освежите память, почитайте про оператор %

[Roma789]

ThunderCat, я знаю,это остаток от деления,я просто не могу догнать сам алгоритм,если ставлю === то всё равно получается слишком много простых чисел

[ThunderCat]

Roma789,

если ставлю === то всё равно получается слишком много простых чисел

Вообще то, по вашей логике, если число не делится нацело на любое число, то оно простое. Хотя на самом деле определение простого числа несколько иное.

Answer 2

[ThunderCat]

где я ошибся?

...
 if (i % j !== 0){ //тут
    b+=1
 }
...

Кроме того, неплохо бы проверять что i <= j, чтобы не гонять лишние циклы

Comments

[Роман]

непонятно про i <= j, зачем это? или автор уже поменял текст вопроса и в его текущей версии это не нужно?

Answer 3

[Роман]

Как вам уже объяснили, ошибка тут

if (i % j !== 0){ //тут
    b+=1
 }

Но так как для вас она не очевидна объясню. Возмем ситуацию когда i=6
и посмотрим как будет работать в данной ситуации внутренний цикл

for (let j = 2; j < i; j++) {
      if (i % j !== 0){
        b+=1
      }
    }

при j = 2 условие не сработает (и это правильно)
при j = 3 условие не сработает (и это правильно)
при j = 4 условие сработает (и это НЕ правильно)
при j = 5 условие сработает (и это НЕ правильно)

итого ваш алгоритм аж 2 раза посчитает что число 6 простое

думаю теперь вам станет понятней в чем ошибка и вы отметите ответы от ThunderCat и Олег как верные))))

ну и от себя добавлю - замените внутренний цикл на такой
for (let j = 2; j <= i/2; j++){
это в 2 раза уменьшит количество циклов. Почему это правильно предлагаю подумать самому))))

Comments

[Roma789]

если я ставлю i % j === 0 то всё равно не правильно подсчитывает кол-во простых чисел

[Роман]

Roma789, b надо увеличивать только тогда, когда текущее i дает остаток, отличный от 0 при делении НА ЛЮБОЕ j большее 1 и меньше или равно чем i/2

[Роман]

Roma789, другими словами, если во внутреннем цикле для конкретного i хоть раз выполнилось ваше условие то число НЕ ПРОСТОЕ и b не должна быть увеличена

[Роман]

Роман, извините, чутка напутал в комментах i и j, сейчас уже исправил, прочитайте и вникните в суть

[Roma789]

Роман,

function g(n) {
  let b = 0;
  for(let i = 2; i <= n; i++){
    for (let j = 2; j <= i/2; j++) {
      if (i % j !== 0 ){
        b+=1
      }
    }
  }
  console.log(b);
};
g(10)

вот казалось бы всё правильно,я увеличиваю счётчик когда i делится с остатком на j,но всё равно результат неправильный,не пойму что неправильного в условии

[ThunderCat]

Roma789, чувак, перестань тупить, простое число делится только на себя и на 1, а ты проверяешь его на деление на каждое число, и если на какое-то не делится, ты его сразу записываешь в простые (причем каждый раз когда не делится), хотя оно может успешно делиться на другие числа.

не пойму что неправильного в условии

В условии все верно (если правильно обрабатывать это условие), а вот логика внутри условия хромает на обе ноги.

[Роман]

Roma789, вот вам правильный ответ, думайте над ним (но плохо уже то, что сами не справились со столь простой задачей)

function g(n) {
  let b = 0;
  for(let i = 2; i <= n; i++){
    let c = true;
    for (let j = 2; j <= i/2; j++) {
      if (i % j == 0 ){
        c = false;
        break;
      }
    }
    if(c==true) b ++;
  }
  console.log(b);
};
g(10);

[Роман]

Roma789, разобрались?