Задача 33593 Дано натуральное число n>1. Проверьте,...

vk35421911

14 февраля 2019 г. в 20:25

Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Программа должна иметь сложность O(корень из n): количество действий в программе должно быть пропорционально квадратному корню из n (иначе говоря, при увеличении входного числа в k раз, время выполнения программы должно увеличиваться примерно в корень из k раз).
(Максимально быстрым способом)

slava191

14 февраля 2019 г. в 21:02

★

function isPrime(n){
for(let i=2; i < n; i++) {
if(n%i==0) return true;
}
return false;
}

Чисто на коленках набросал, как идея, работать должно, но я не компилировал и соответсвует ли оно вышенаписанной сложности тоже не проверял. Язык JS