Можно ли считать данный код реализацией решета Эратосфена на JS?

Question

let arr = [];
for (let i = 0; i < 10001; i++) {
  arr[i] = i;
}
for (let z = 2, i = 3, y = 5, x = 7, e = 11, q = 0; q < 10001; z += 2, i += 3, y += 5, x += 7, e += 11, q++) {
  arr[z] = 0;
  arr[i] = 0;
  arr[y] = 0;
  arr[x] = 0;
  arr[e] = 0;
}
for (let i = 1; i < 1000; i++) {
  document.write(arr[i] + " " + i + "<br/>")
}

слева от i в цикле

for(let i = 1; i<1000; i++) {
    document.write(arr[i] + " " + i + "<br/>")
}

может выводится либо 0, и тогда это составное число (по моей задумке), либо сама i, тогда это простое число.

Пока что руки не дотянулись проверить везде ли где ноль стоит простое число (с помощью более простого алгоритма который не даст осечек 100%).
В общем простите за незнание теории чисел, то есть за то что я не могу лично математически доказать, что оно выводит только простые числа. Но я каждый день надеюсь, что программирование не только для знающих математику (некоторые области программирования)

Answer 1

Нашел код ниже - здесь, суммы разные, твой код можно считать Частной реализацией решета Эратосфена :)

let arr = [];

for (let i = 2; i < 10001; i++) {
  arr[i] = true;
}

let p = 2;
while (p * p < 10001) {
  for (i = 2 * p; i < 10001; i += p) arr[i] = false;
  for (i = p + 1; i < 10001; i++) {
    if (arr[i]) break;
  }
  p = i;
}

let sum = 0;
for (i = 0; i < arr.length; i++) {
  if (arr[i]) sum += i;
}
console.log(sum);

"Исправил" твой код, максимум 121, ибо у тебя работать будет только до 11*11

let max = 121;
let arr = [];

for (let i = 0; i < max - 1; i++) {
  arr[i] = i + 2;
}

// let z = 2, i = 3, y = 5, x = 7, e = 11, q = 0;
let z = arr.indexOf(2),
  i = arr.indexOf(3),
  y = arr.indexOf(5),
  x = arr.indexOf(7),
  e = arr.indexOf(11),
  q = 0;

while (q < max) {
  z += 2;
  i += 3;
  y += 5;
  x += 7;
  e += 11;
  arr[z] = 0;
  arr[i] = 0;
  arr[y] = 0;
  arr[x] = 0;
  arr[e] = 0;
  q++;
}
console.log(Object.values(arr));

summ = 0;
for (let e in arr) {
  summ += arr[e];
}
console.log(summ);

Answer 2

Этот код не является валидной реализацией решета дедушки Эратосфена.

При работе решета помечаются все числа, кратные уже найденным простым. Всем найденным. Здесь же по какой-то причине выбраны только пять первых. Нетрудно увидеть, что числа 169, 221 или 289 будут помечены как простые. Дальше можно не продолжать

БЛОГ НА HUSL

Можно ли считать данный код реализацией решета Эратосфена на JS?

Ответы (2 шт):