Проверьте простое число

Решение

Простое число — это натуральное число больше 1, которое делится только на 1 и на себя. Разберу несколько подходов от базового к оптимизированному.

Подход 1: Базовый (O(n))

function isPrime(n: number): boolean {
  // Граничные случаи
  if (n <= 1) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  
  // Проверяем делители от 3 до n
  for (let i = 3; i < n; i += 2) {
    if (n % i === 0) return false;
  }
  
  return true;
}

Анализ:

• Временная сложность: O(n)
• На большие числа очень медленно
• Пропускаем чётные числа (кроме 2)

Подход 2: Оптимизированный (O(√n)) — РЕКОМЕНДУЕМЫЙ

function isPrime(n: number): boolean {
  // Граничные случаи
  if (n <= 1) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  
  // Проверяем делители до √n
  // Если n имеет делитель > √n, то имеет и < √n
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false;
  }
  
  return true;
}

Математическое обоснование:

• Если n = a × b, где a ≤ b, то a ≤ √n
• Достаточно проверить делители до √n
• Пример: для n=100, проверяем до 10

Временная сложность: O(√n) ~ 1000x быстрее для n=1,000,000

Примеры:

isPrime(2);   // true
isPrime(17);  // true (проверяем до 4)
isPrime(4);   // false
isPrime(1);   // false
isPrime(0);   // false
isPrime(-5);  // false
isPrime(97);  // true (проверяем до 9)
isPrime(100); // false

Подход 3: С использованием Math.sqrt

function isPrime(n: number): boolean {
  if (n <= 1) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  
  const sqrt = Math.sqrt(n);
  
  for (let i = 3; i <= sqrt; i += 2) {
    if (n % i === 0) return false;
  }
  
  return true;
}

Особенность: Math.sqrt вычисляется один раз, может быть немного быстрее

Подход 4: С проверкой на отрицательные и типов

function isPrime(n: number): boolean {
  // Типизация
  if (!Number.isInteger(n)) return false;
  if (n < 2) return false;  // Простые числа >= 2
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  
  // O(√n) проверка
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false;
  }
  
  return true;
}

Подход 5: Оптимизация для малых чисел

function isPrime(n: number): boolean {
  if (!Number.isInteger(n)) return false;
  if (n < 2) return false;
  
  // Быстрая проверка известных простых чисел
  if (n === 2 || n === 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  
  // Проверяем числа вида 6k ± 1
  // Все простые > 3 имеют форму 6k ± 1
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  
  return true;
}

Почему 6k ± 1?

• Все простые числа > 3 имеют форму 6k - 1 или 6k + 1
• 6k, 6k + 2, 6k + 3, 6k + 4 всегда делятся на 2 или 3
• Пример: 5 = 6×1 - 1, 7 = 6×1 + 1, 11 = 6×2 - 1, 13 = 6×2 + 1

Производительность: ~3x быстрее чем подход 2

Подход 6: Вероятностный (Miller-Rabin) для огромных чисел

function isPrimeMillerRabin(n: number, k: number = 5): boolean {
  if (n < 2) return false;
  if (n === 2 || n === 3) return true;
  if (n % 2 === 0) return false;
  
  // Разлагаем n-1 на 2^r × d
  let d = n - 1;
  let r = 0;
  while (d % 2 === 0) {
    d /= 2;
    r++;
  }
  
  // k раундов тестирования
  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (n - 3));
    let x = Math.pow(a, d) % n;
    
    if (x === 1 || x === n - 1) continue;
    
    let composite = true;
    for (let j = 0; j < r - 1; j++) {
      x = (x * x) % n;
      if (x === n - 1) {
        composite = false;
        break;
      }
    }
    
    if (composite) return false;
  }
  
  return true;
}

Использование: для чисел > 10^15 (вероятностный алгоритм)

Тестирование

const testCases = [
  [2, true],
  [3, true],
  [4, false],
  [17, true],
  [1, false],
  [0, false],
  [-5, false],
  [97, true],
  [100, false],
  [101, true],
  [1000000007, true],
];

testCases.forEach(([n, expected]) => {
  const result = isPrime(n as number);
  console.log(`isPrime(${n}) = ${result}, expected ${expected} ${result === expected ? '✓' : '✗'}`);
});

Сравнение подходов

Рекомендация для интервью

Начните с подхода O(√n) — он показывает:

• Понимание математической оптимизации
• Правильную обработку граничных случаев
• Чистый и читаемый код

Если спросят про оптимизацию, упомяните 6k ± 1 форму и Miller-Rabin для очень больших чисел.

Ключевые моменты:

• Простые числа >= 2
• √n оптимизация сокращает проверки в 1000x раз
• Чётные числа (кроме 2) сразу исключаются
• Для n=1,000,000 проверяем до 1,000 вместо 1,000,000