Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Введите число:");
String data = "";
Integer x;
try {
data = in.readLine();
} catch (IOException ex) {
System.err.println(ex.getLocalizedMessage());
return;
}
try {
x = Integer.parseInt(data);
} catch(NumberFormatException ex) {
System.out.println("Вы ввели не число!");
return;
}
if(x <= 0) {
System.out.println("Число должно быть положительным!");
return;
}
HashMap friends_nums = new HashMap<Integer, Integer>();
for(int i = 0; i <= x; i++) {
int s = 0;
for(int y = 1; y < i; y++) {
if(i % y == 0) { s += y; }
}
int t = 0;
for(int y = 1; y < s; y++) {
if(s % y == 0) { t += y; }
}
if(t == i && s != i && !friends_nums.containsValue(i)) { friends_nums.put(i, s); }
}
if(friends_nums.isEmpty()) {
System.out.println("Дружественных пар не найдено!");
} else {
System.out.println("Найдены следующие дружественные числа:");
Object[] one = friends_nums.keySet().toArray();
Object[] two = friends_nums.values().toArray();
for(int i = 0; i<friends_nums.size(); i++) {
System.out.println(one[i] + " и " + two[i]);
}
}
}
Дружественными числами называются два различных натуральных числа, для которых сумма всех собственных делителей первого числа (сумма всех делителей, отличных от самого числа) равна второму числу и сумма всех собственных делителей второго числа равна первому числу. Примеры дружественных чисел: 220 и 284. Делители числа 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 (в сумме дают число 284); делители числа 284: 1, 2, 4, 71, 142 (в сумме 220). Примеры других пар дружественных чисел: 2620 и 2924, 17296 и 18416. Написать программу, которая по заданному натуральному числу N находит все пары дружественных чисел, не превосходящих N.
> строки 1-16
Чтение целого числа давно пора оформить в функцию. В других лабах тоже пригодится.
> for(int y = 1; y < i; y++) {
Искать делители делением по самое число... как бы мягко выразиться... некрасиво. Но для мелких чисел как в задаче - конечно пофиг. Вычисление суммы делителей числа стоит вынести в функцию.
> !friends_nums.containsValue(i)
Чтобы убить одинаковые пары достаточно было тупого сравнения i<s или i>s. Хешмап это оверкилл. Да еще и заставили бедного хешмапа заниматься неподобающей ему операцией - проверкой того, что он содержит заданное значение.
>Чтение целого числа давно пора оформить в функцию. В других лабах тоже пригодится.
И так потихоньку у тебя вырастает самописная библиотека для упрощения и обхода говен в стандартной библиотеке.
>Хешмап это оверкилл
Вот и выросло поколение, которое не уважает бит массивы.
Уникальные сочетания степеней.
Например довольное большое число:
2^3*3^4*11^2
i=2 for [0..3]
j=3 for [0..4]
k=11 for [0..2]
for each (s=i*j*k)
sum+=s;
Всего-то собрать 4*5*3=60 сумм.
Причем тут "делить/умножать на два сдвигом?".
Поясните мысль.
Это корень.
Насчет бинарной арифметики и сдвигов - пост ниже.
Там просто надо найти позицию младшей единицы, сдвинуть число, убрав всё младшие нули.
Потом пройтись по нечетным до корня (уже нечетного числа) и сложить.
После чего умножить на чудесный коэфициент.
Упростил код с разложением. Это будет последняя версия до тех пор, пока кто-нибудь не обгонит ее. 37 пар / 4.45s. http://ideone.com/pBmRP3
> нормальный алгоритм типа этого
Ну так разложение что-то типа этого и есть. Считаем сколько раз c[i] встречается каждый из простых множителей p[i]. Затем применяем простенькую формулку product(1+p[i]...+p[i]^c[i]) и вычитаем из нее само число (т.к. его не считают своим же делителем).
Как вариант - можно попробовать не разбивать числа на множители, а строить их. При этом смотреть не то, что сумма делителей одного числа, не включая его, дает другое и наоборот, а более простое но равносильное правило - сумма всех делителей одного числа (включая его самого) равна сумме всех делителей второго...
>Выжал всё что мог из кода на C++
> всё равно получилось медленнее, чем на хаскелле оО.
Стыдоба ебучая.
Ну ведь говно полное. Надо головой думать, например - искать количество делителей степени 2 - n, потом идти по нечетным до корня от деления на 2^n.
Ну и потом умножать примерно на 2^(n)-1.
А потом вот такие вот люди делают бенчи в которых жаба быстрей си, сисярп.assParallel() быстрее ассемблера, а хацкель быстрей плюсов.
P.S. Если прога на Си позиционируется как "быстрая" и не рвет прогу на хаскеле раз в 10 - то эта сишная прога говно. Я более чем уверен, что на си алгоритм с факторизацией отрабатывал бы на порядок быстрее чем на хаскеле.
Просто нужно было очень быстро решить поставленную задачу. Забыл сразу добавить, что да, очень корявенько. Самый натуральный говнокод. Главное, что оно работает.
Чтение целого числа давно пора оформить в функцию. В других лабах тоже пригодится.
> for(int y = 1; y < i; y++) {
Искать делители делением по самое число... как бы мягко выразиться... некрасиво. Но для мелких чисел как в задаче - конечно пофиг. Вычисление суммы делителей числа стоит вынести в функцию.
> !friends_nums.containsValue(i)
Чтобы убить одинаковые пары достаточно было тупого сравнения i<s или i>s. Хешмап это оверкилл. Да еще и заставили бедного хешмапа заниматься неподобающей ему операцией - проверкой того, что он содержит заданное значение.
И так потихоньку у тебя вырастает самописная библиотека для упрощения и обхода говен в стандартной библиотеке.
>Хешмап это оверкилл
Вот и выросло поколение, которое не уважает бит массивы.
> .keySet().toArray()
> .values().toArray()
> .values().toArray()
Что не сделаешь, чтобы не читать документацию.
Эм, это обо мне? ;(
А то введите число, введите число...
http://ideone.com/m656Ec
пруф:
http://ideone.com/6XwxCw
http://ideone.com/mcPaDf
P.S. Си все таки быстрее хаскеля 😉
http://ideone.com/hLrgiR
Так-что в итоге это до корня. Сразу до корня я не додумался.
>upperLimit = (x / d);
Тоже кал, хоть в этом есть зачатки правильной идеи. Или компилер такое нынче хавает?
Я бы еще попробовал разложить на степеня простых чисел и потом искать сочетания.
Но лень.
Например довольное большое число:
2^3*3^4*11^2
i=2 for [0..3]
j=3 for [0..4]
k=11 for [0..2]
for each (s=i*j*k)
sum+=s;
Всего-то собрать 4*5*3=60 сумм.
http://ideone.com/L0iWpQ
Тормозной хаскель снова порвал сишечку по производительности.
P.S. Лишнее подтверждение того, что алгоритм важнее микрооптимизаций.
Очевидно фикс до поры до времени. Теперь в 2 раза больше порвал.
>хаскель снова порвал сишечку по производительности.
И вообще не провоцируйте меня.
Integer (BigInteger) => Int
Но походу этот козарь и ещё несколько борманд оставил в рукаве, чтобы резко обогнать сишку перед финишем.
Сикодеры нервно курят в сторонке перед надёжным хаскеллом
Походу sqrt настолько тормозной, что десяток-другой умножений спокойно его обгоняет.
Фу.
> Фу.
Надо d <= sqrt(x)?
int upper=sqrt(x)+1;
while(d <= upper)
Поясните мысль.
Это корень.
Насчет бинарной арифметики и сдвигов - пост ниже.
Там просто надо найти позицию младшей единицы, сдвинуть число, убрав всё младшие нули.
Потом пройтись по нечетным до корня (уже нечетного числа) и сложить.
После чего умножить на чудесный коэфициент.
http://ideone.com/uqIpBU
Для 35 пар, собиралось с O2:
Так что где еще фу.
Имхо стоит асимптотику оптимизнуть в алгоритме с разложением, а не задрачивать корни и сдвиги вместо делений...
http://govnokod.ru/12067#comment159249
http://govnokod.ru/12067#comment159266
цена оптимизации выростет.
Ну это проще простого, правда хацкель мне даже читать трудновато.
А писать своё лень.
http://ideone.com/pBmRP3
> нормальный алгоритм типа этого
Ну так разложение что-то типа этого и есть. Считаем сколько раз c[i] встречается каждый из простых множителей p[i]. Затем применяем простенькую формулку product(1+p[i]...+p[i]^c[i]) и вычитаем из нее само число (т.к. его не считают своим же делителем).
http://ideone.com/mN3tO7
Ололо. Я тебя обогнал ничго не делая: 37 пар / 1.76s
37 / 4.3
Ну его нахуй этот хаскель, пойду на крестах напишу.
30 пар:http://ideone.com/kyLGMK
60 пар:http://ideone.com/mIoEKj
P.S. Интересно до скольки мог досчитать исходный алгоритм ОП'а за час 😉
Не нашёл пару (1184,1210)
http://ideone.com/dhYoqD
fxd.
Досадный баг.
Если найти более эффективный алгоритм факторизации, можно будет значительно ускорить алгоритм.
> всё равно получилось медленнее, чем на хаскелле оО.
Стыдоба ебучая.
Ну ведь говно полное. Надо головой думать, например - искать количество делителей степени 2 - n, потом идти по нечетным до корня от деления на 2^n.
Ну и потом умножать примерно на 2^(n)-1.
А потом вот такие вот люди делают бенчи в которых жаба быстрей си, сисярп.assParallel() быстрее ассемблера, а хацкель быстрей плюсов.
"Выжал всё что мог из кода на C++" - не значит, что я написал эффективный алгоритм.
Напишите версию быстрее чем текущая (http://ideone.com/mcPaDf), раз уж код такое говно.
запросто:
http://ideone.com/nmdGc7
0.53 ms
P.S. Если прога на Си позиционируется как "быстрая" и не рвет прогу на хаскеле раз в 10 - то эта сишная прога говно. Я более чем уверен, что на си алгоритм с факторизацией отрабатывал бы на порядок быстрее чем на хаскеле.