Liczba pierwsza: naiwnie i do pierwiastka

Algorytmy z egzaminu różnymi sposobami - JavaScript od podstaw: konsola (JavaScript)

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i siebie. Naiwnie sprawdzamy wszystkie dzielniki od 2 do n - 1. Ale jeśli n = a * b, to któryś z czynników jest nie większy niż pierwiastek z n, więc wystarczy sprawdzać, dopóki `d * d <= n`. Licznik dzieleń pokazuje różnicę dla dużej liczby pierwszej.

let divisions = 0;

function isPrimeNaive(n) {
  if (n < 2) return false;
  for (let d = 2; d < n; d++) {
    divisions++;
    if (n % d === 0) return false;
  }
  return true;
}

function isPrimeSqrt(n) {
  if (n < 2) return false;
  for (let d = 2; d * d <= n; d++) {
    divisions++;
    if (n % d === 0) return false;
  }
  return true;
}

for (const n of [97, 7919]) {
  divisions = 0;
  const a = isPrimeNaive(n);
  const naive = divisions;
  divisions = 0;
  const b = isPrimeSqrt(n);
  console.log(`${n}: ${a} ${b}, dzieleń naiwnie ${naive}, do pierwiastka ${divisions}`);
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu JavaScript od podstaw: konsola·Zaloguj się, aby zapisać postęp na koncie.