Какой алгоритм можно применить при проверки числа на простое ли оно?

Question

[Boris009]

На днях попалось на слух определение простого числа и я решил написать под это дело функцию
Но наткнулся на момент, что если число будет очень большое, то и перебор становится длинным
Можно ли как-то сократить перебор миллиона раз при проверке числа 1000000?

function checkForPerfectNumber(num) {
  const numbers = []
  
  for(let i = 1; i < num; ++i) {
    const rest = num % i
    if(!rest) numbers.push(i)
  }
  
  const count = numbers.reduce((acc, val) => acc + val, 0)
  
  return count === num
}

Comments

[GavriKos]

А для чего в приведенном коде вообще numbers? Почему цикл не прерывать сразу как только нашелся первый делитель? Это кнчн не поможет при сильно больших числах, но ваш алгоритм выглдят избыточным.

[historydev]

Полагаю проблема в зависании?

Answer 1

[Mercury13]

Если нужно проверить а) точно, и б) одно; в) не очень большое число (миллион тоже небольшое) — ничего нет лучше, чем проверка нечётных чисел до корня из n. То есть до 1000.

Если точно, много и небольшие — то придётся держать список простых чисел, пополняя его, когда попадётся слишком большое число. Список тоже до корня из n. Допустим, если предел — int4 (≈4 млн), то нужно держать только список до 65535, это пара тысяч чисел.

Если число совсем небольшое и может быть где-то в списке — ищем его хитрой разновидностью поиска: проверяем 1-е число, 2-е, 4-е и т.д., пока не определим диапазон, где может быть число. И в этом диапазоне ищем двоичным поиском.

В криптографии востребован неточный поиск — «число, скорее всего, простое». Но об этом не будем, вы не настолько круты. Тут уже основано на том, что держим таблицу небольших простых чисел и делим на них, а затем гоняем неточные тесты.

PERFECT number — это СОВЕРШЕННОЕ число. Это не то (сумма всех делителей равняется самому числу), и для теста на совершенное число тоже надо проверять до корня из n — если a делится на b, то добавляем и b, и a/b (кроме случаев, когда b=1 и b²=a, разумеется). Если есть простые числа до корня из n — тоже можно разбить на простые множители (один из множителей может быть больше корня из n!) и подключить комбинаторику, чтобы заполучить остальные.

Answer 2

[pfg21]

погуглить
https://habr.com/ru/articles/468833/
https://ru.wikipedia.org/wiki/Тест_простоты