Java

Говорит, что программа слишком долго выполняется. Как её ускорить?

Нужно понять, простое ли число или нет
[https://www.codewars.com/kata/5262119038c0985a5b00029f/train/java]

public static boolean isPrime(int num) {
    if (num < 2) return false;
    int divisorsCount = 2;
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            divisorsCount++;
        }
    }
    return (divisorsCount == 2);
}

::: Execution Timed Out (16000 ms) :::
Владимир Дершень
Владимир Дершень
1 675
Самое простое, это покидать цикл, когда находится больше 2 делителей
Ахо Исаев
Ахо Исаев
11 272
Лучший ответ
Владимир Дершень А почему происходит ошибка?

public static boolean isPrime(int num) {
if (num < 2) return false;
int divisorsCount = 2;
for (int i = 2; i < num; i++) {
if (num % i == 0) {
divisorsCount++;
}
divisorsCount > 2? break : continue;
}
return (divisorsCount == 2);
}
public static boolean isPrime(int num) {
if (num < 2) { return false; }
if (num % 2 == 0) { return num == 2; }
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) { return false; }
}
return true;
}
MP
Maks Planokurov
90 117
Владимир Дершень Я понял, что цикл исключает чётные числа, но почему сразу нужно проверять на i²? Это как работает? Не может быть, что в пределах этого, может скрыться ещё одно число? Можете объяснить этот момент?
Аркадий, уж сколько раз эта задача решена за 30 лет по-вашему? Неужели трудно нагуглить оптимизированные решения?
Простые числа - только нечетные (кроме 2). Если четное - сразу нет. Если нечетное - пробегать не по КАЖДОМУ числу от 2 до num, а через одно, только по нечетным делителям.
Опять же цикл < num, если num не захватывает, откуда вы получите 2 делителя? В конце вы определяете простоту по 2 делителям. Будет 1. У вас простые числа будут непростыми.
Дальше, нет смысла бегать до самого числа num, т. к. самый большой делитель (кроме самого числа) не может превышать квадратного корня из num + 1. По этой планке надо ограничить цикл.
Еще можно проверять не все нечетные делители, а только простые, еще больше ограничив цикл.
Отсюда и овертайм у вас.

https://hd01.ru/info/kak-opredelit-prostoe-chislo-ili-net/
Витек Штольц
Витек Штольц
55 095
Ну разумеется! Для codewars нужно ведь что-то побыстрее!. Классический метод Фибоначчи, его модификация с ужè готовым списком primes (получаемым, естественно, безо всякого сита Эратосфена !) и метод теста на составность П. Ферма - это всё глубокая древность. Так, например, Леонардо жил в двенадцатом-тринадцатом веках, Пьер во времена неистового гастонца Д'Артаньяна, испанки Анны Австрийской и кардинала Ришельё.. Да, много воды утекло с тех пор!
｡◕‿◕｡
Илья Ибрагимов
Илья Ибрагимов
29 440
Леша Сапкалов С самого начала, Миша! Нету жизни! Потому что ты говоришь о программе.

Похожие вопросы