Это потому, что метод Scanner.nextInt
не использует символ последней новой строки вашего ввода и, следовательно, newline потребляется в следующий вызов Scanner.nextLine
.
Вы столкнетесь с аналогичным поведением, когда вы используете Scanner.nextLine
после Scanner.next()
или любого метода Scanner.nextFoo
(кроме самого nextLine
).
Обход проблемы:
Scanner.nextLine
вызов после Scanner.nextInt
или Scanner.nextFoo
, чтобы потреблять остальную часть этой линии, включая newline int option = input.nextInt();
input.nextLine(); // Consume newline left-over
String str1 = input.nextLine();
Scanner.nextLine
и преобразуете свой ввод в нужный формат. Например, к целому числу с использованием метода Integer.parseInt(String)
. int option = 0;
try {
option = Integer.parseInt(input.nextLine());
} catch (NumberFormatException e) {
e.printStackTrace();
}
String str1 = input.nextLine();
Функция isPrime()
вызывается слишком много раз в primefactors
. Например, i == 2
и в n
имеется много дивизоров 2
. Верхний вызов (isPrime(i))
в порядке. Однако внутри цикла while (n % i == 0)
вы проверяете isPrime(n)
после каждого деления n /= 2;
. Итак, если начальный n
равен 100
, функция isPrime()
вызывается для 50
и следующего цикла для 25
. В этом нет смысла. Я думаю, что это самая большая проблема здесь, так как даже если isPrime
работает в линейном режиме, слишком много можно называть его много раз во внутреннем цикле.
Можно выйти из цикла для i
в двух случаях: n
равно 1
после делений или n
для уверенного простого, если i
больше sqrt(n)
.
public String primefactors(int n) {
String factors = "";
int max_divisor = sqrt(n);
for (int i = 2; i <= max_divisor; i++) {
if (isPrime(i)) {
while (n % i == 0) {
n /= i;
if (n == 1)
factors = factors + Integer.valueOf(i).toString();
else
factors = factors + Integer.valueOf(i).toString() + "*";
}
max_divisor = sqrt(n);
}
}
// check for the last prime divisor
if (n != 1)
factors = factors + Integer.valueOf(n).toString();
return factors;
}
Даже после этого улучшения (и sqrt(n)
как максимальный предел в isPrime()
), ваш алгоритм будет иметь линейную сложность O(n)
, так как для i
существует не более sqrt(n)
петель, а максимальное число зондов для prime в isPrime
равно также sqrt(n)
.
Да, это можно сделать лучше, выбрав лучшие алгоритмы для isPrime()
. Даже если вам не разрешено использовать жестко заданную таблицу простых чисел, можно создать такую таблицу поиска во время выполнения (если памяти достаточно). Таким образом, можно использовать автоматически сгенерированный список простых чисел, организованных в порядке возрастания, чтобы исследовать заданное число до sqrt(n
). Если i
становится больше, чем sqrt(n)
, это означает, что следующее простое число найдено, и оно должно быть добавлено к таблице поиска, а isPrime()
должно возвращать true
.
Пример
Предположим, что isPrime
вызывается для 113
. В этот момент таблица поиска имеет список предыдущих простых чисел: 2,3,5,7,11,13...
. Итак, мы пытаемся разделить 113
на элементы из этого списка до sqrt(113)
(while (i <= 10)
). После попытки 2,3,5,7
следующий элемент в списке 11
слишком велик, поэтому 113
добавляется в список простых чисел, а функция возвращает true
.
Другие алгоритмы может дать лучшую производительность в худшем случае. Например, сито Эратосфена или сито Аткина можно использовать для эффективного предкомпьютерного списка простых чисел до заданного n
с наилучшей сложностью O(n)
для наилучшей реализации. Здесь вам нужно найти все простые числа до sqrt(n)
, поэтому для создания такого списка требуется O(sqrt(n))
. После создания такого списка вам нужно попытаться разделить ваш ввод по номерам, это список, который занимает не более sqrt(n)
зондов. Таким образом, сложность алгоритма - O(sqrt(n))
. Однако предположим, что ваш вход 1024
равен 2
мощности 10
. В этом случае первый алгоритм будет лучше, так как он не перейдет к простым числам, большим 2
.
Вам действительно нужна функция isPrime ()?
С гибким мышлением Если мы посмотрим поближе, кажется, вам не нужно искать все простые числа в некотором диапазоне. Вам нужно было найти все простые делители одного заданного целого числа. Однако, если мы попытаемся разделить n
на все целые числа в диапазоне до sqrt(n)
, что также является хорошим решением. Даже если такое целое число не является простым, оно будет пропущено из-за условия n % i == 0
, так как все простые числа, меньшие, чем тестируемое целое число, уже удалены из n
, так что простое модульное деление здесь совпадает с isPrime()
. Полное решение с O(sqrt(n))
сложностью:
public String primefactors(int n) {
String factors = "";
int max_divisor = sqrt(n);
for (int i = 2; i <= max_divisor; i++) {
while (n % i == 0) {
n /= i;
max_divisor = sqrt(n);
if (n == 1)
factors = factors + Integer.valueOf(i).toString();
else
factors = factors + Integer.valueOf(i).toString() + "*";
}
}
// check for the last prime divisor
if (n != 1)
factors = factors + Integer.valueOf(n).toString();
return factors;
}
Также возможно разделить функцию, чтобы избежать проверки if (n == 1)
во внутреннем цикле, однако это не меняет сложность алгоритма.
Поскольку n
меньше фиксированного числа (109), просто используйте таблицу, содержащую все примитивы & lt; = 109, вместо генерации их динамически. Или, по крайней мере, сначала генерируйте примочки, используя сито эрастостен или аткин. Скорректированная таблица предпочтительнее, но использование сита для генерации таблицы динамически также будет ускорять процесс. Функция isPrime()
, которую вы внедрили, является убийцей производительности.