Данная небольшая задача уже не решилась "с наскоку" и потребовала
немного подумать над алгоритмом. Также, помимо применения в
программе новых конструкций языка java, реализовал в ней
пользовательский ввод через параметры командной строки, все файлы
скомпилировал в один jar архив, передал его через ssh
и запустил на удаленном сервере.
Онлайн-калькулятор
для проверки вычислений и правильный ответ на задачу
прилагаются.
Простые делители числа 13195 - это 5, 7, 13 и
29.
Какой самый большой делитель числа 600851475143,
являющийся простым числом?
При целочисленном делении числа, получается сразу два делителя:
максимальный и минимальный.
Например, число 15
можно представить как произведение 3 на 5. Больший
делитель, в свою очередь, также может быть разложен на множители.
При этом, если перебирать делители от меньшего к большему, то первый найденный делитель будет априори минимальным и простым.
Также нет необходимости проверять все делители от 2 до самого раскладываемого числа. Достаточно проверить делители только до корня квадратного из раскладываемого числа. Если до него делителей числа нет, то и дальше их не будет и проверяемое число является простым.
Кроме того, все четные числа делятся на 2. Потому, проверив делимость числа на 2 можно не проверять его делимость на 4, 6 и т.д.
Также при разложении числа на простые множители не нужно каждый раз проверять все множители.
Исходный код программы разделен два класса, размещенных в отдельных файлах.
src/ Calculator.java Solution.java
Класс Solution служит для получения пользовательского ввода, а также содержит метод main().
// Solution.java
public class Solution {
public static void main(String[] args) {
long num = (args.length > 0) ?
(Long.parseLong(args[0])) : (600851475143L);
Calculator calculator = new Calculator();
long answ = calculator.getMaxPrimeDiv(num);
System.out.println("Answer is " + answ);
}
}
Число, максимальный простой делитель которого необходимо найти, передается пользователем программе через параметры командной строки:
Число 1000 принимается методом main() в виде
элемента массива args[0] содержащего строку "1000".
Чтобы преобразовать строку в число, применил предопределенный
класс Long и его статический метод parseLong().
Программу можно запускать также и без параметров (args.length == 0):
В этом случае программа вычисляет максимальный простой делитель дефолтного числа 600851475143 (из условий 3 задачи Эйлера).
Для вычисления ответа, с помощью конструктора создал объект calculator - экземпляр класса Calculator, содержащий необходимые методы для вычислений.
//Calculator.java
class Calculator {
long getMinDiv(long number, long div) {
if((number % div == 0) && (div * div <= number)) {
return div;
}
div = (div % 2 == 0) ? (div + 1) : (div);
for (long i = div; i * i <= number + 1; i += 2) {
if (number % i == 0)
return i;
}
return 1;
}
Метод getMinDiv() принимает число и начальный делитель в
качестве аргументов и возвращает минимальный простой делитель
числа.
При этом проверяются только нечетные делители и
только до корня квадратного из проверяемого числа.
//Calculator.java - продолжение
long getMaxPrimeDiv(long num) {
long minDiv = 2;
do {
minDiv = getMinDiv(num, minDiv);
num = num / minDiv;
} while (minDiv != 1);
return num;
}
}
Метод getMaxPrimeDiv() принимает число и раскладывает его на множители до тех пор, пока оно не перестанет раскладываться. Последний полученный множитель и будет искомым максимальным простым делителем.
Продолжаю упражняться в работе с удаленным сервером. Соберу исходный код программы в один jar-файл, скопирую его на сервер по ssh и запущу там.
В данный момент структура программы имеет следующий вид:
problem-3/
src/
Calculator.java
Solution.java
Компилирую файлы с исходным кодом:
Где:
Скомпилированные файлы появились в отдельной папке:
problem-3/
bin/
Calculator.class
Solution.class
src/
Calculator.java
Solution.java
Вопросы компиляции java-кода более подробно описаны в статье:
Чтобы создать архив классов, понадобится файл-манифест manifest.mf
problem-3/
bin/
Calculator.class
Solution.class
manifest.mf
src/
Calculator.java
Solution.java
В нем нужно указать главный класс (содержащий метод main()) и путь к скомпилированным классам:
main-class: Solution class-path: bin/
Собираю jar-файл:
Где:
Собранный jar-файл появился в текущей директории:
problem-3/
bin/
Calculator.class
Solution.class
manifest.mf
Solution.jar
src/
Calculator.java
Solution.java
Копирую jar-файл на удаленный сервер:
Краткий гайд, если возникнут вопросы:
Зашел на сервер:
... и запустил jar-файл:
# java -jar Solution.jar Answer is 6857
Здесь возможно вылезет проблема, заключающаяся в том, что на
сервере и компьютере установлены разные версии java.
Проверить версию java можно командой:
При необходимости можно установить или выбрать нужные версии и
перекомпилировать все заново.
Меняем версию java:
... и компилятора javac:
Еще несколько полезных статей, чтобы не повторяться:
В данной программе применил несколько новых конструкций языка java: