+67
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
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.
Запостил: 
JavaCoder,
06 Ноября 2012
Follow us!
Чтение целого числа давно пора оформить в функцию. В других лабах тоже пригодится.
> 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 - то эта сишная прога говно. Я более чем уверен, что на си алгоритм с факторизацией отрабатывал бы на порядок быстрее чем на хаскеле.