![]()
Light or Dark
![]() offline
Опыт:
7,275Активность: |
Оптимизация задачи
Помогите пожалуйста!нужно решить задачу нахождение суммы простых делителей.ограничение по времени 2 секунды.число вводится до 10 в 9 степени.
я решил так(язык pascal): Код:
но вот проблема-не проходит по времени(>2 секунд)...пожалуйста помогите,что надо сделать! Light or Dark добавил: так что,никто не поможет????((((((((((( Light or Dark добавил: ну плиииз!помогите! |
![]() |
#1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
MF
Что-то вокруг не так
![]() ![]() offline
Опыт:
26,594Активность: |
Light or Dark я не думаю что ты вообще находишь простые делители, так как ты просто убеждаешься что число делится на i, но оно не обяз простое.
|
![]() |
#2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
Код:
Отредактировано J, 02.05.2009 в 03:08. |
![]() |
#3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
MF
Что-то вокруг не так
![]() ![]() offline
Опыт:
26,594Активность: |
|
![]() |
#4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
... это бы точно работало бы если мы на простые числа проверяли все числа, а не только делаители, а раз я проверяю только делители то я неуверен, ну нихачу просто думать |
![]() |
#5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
MF
Что-то вокруг не так
![]() ![]() offline
Опыт:
26,594Активность: |
J по идее вполне норм, ускорение процесса будет налицо. Если сначала проверять, что число простое, а потом делитель ли, то итераций будет больше. А так вроде норм.
|
![]() |
#6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Light or Dark
![]() offline
Опыт:
7,275Активность: |
у меня все верно(ищет моя прога делители)....спросил у зав. кафедры-она говорит правильно,но надо идти до round(sqrt(ch)) (первый фор). но у меня это не работает((( |
![]() |
#7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
Цитата:
|
|
![]() |
#8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
MF
Что-то вокруг не так
![]() ![]() offline
Опыт:
26,594Активность: |
Light or Dark
Не правильно, если введешь ch = 4 то при i = 4 условие сработает и 4 приплюсуется, а оно как бэ не простое число. MF добавил: Хотя... наверное я не прошарил, извинтиляюсь. |
![]() |
#9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
» asm Код:
ну грубо говоря я все загнал в регистры... но 0ffffffffh считает чувствительно долго (+ не факт что правильно) ADOLF добавил: на 15 - сумма 9 (1,3,5) вестимо на 16 - сумма 3 (1,2) ADOLF добавил: 10000000h (там чуть больше) - около четырех сек |
![]() |
#10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
а, нужно ведь сумма а не список, чуть подправил код
J добавил: ADOLF мой тоже 0x10000000 делает около четырех сек =p |
![]() |
#11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
J, у тебя какой проц ?) и прогони какое то конкретное число - результаты сравним...
|
![]() |
#12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
2,4 гГр.
J добавил: но это толкьо для 0x10000000 выполняется так быстро, чем больше список постых чисел тем будет дольше PS 1 это не простое число J добавил: PPS я вкрутил таймер, он оЧеНь точный, потому лучше отклчюить все что тормозит |
![]() |
#13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
1 не простое? лол) ну там всеравно, либо 0 либо 1 писать в регистр) только таймер я не прикручу) сейчас резулты сравню
// атлон 2к, 1.666 ADOLF добавил: как ни странно но у мну результат равен +1 к твоему (ну я понял да 1 надо выпилить в начале) |
![]() |
#14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
ADOLF простое число нельзя представить в виде множителей простых чисел
1 = 1*1 получается 1 не простое число почтиай вики и посмотри списки простых чисел, там нигде нету еденицы |
![]() |
#15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
10000002h - 3.7 сек у тебя, сейчас себя проверю...
ADOLF добавил: так, к своей тулзу прикручивать таймер мне влом, твою из под оли запускать тоже...) |
![]() |
#16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
=) вот чем плох асм) а мне всеволишь потребовалось перенести пару файликов из своей старой игры и добавить пару строчек, что заняло полторы минуты) Отредактировано J, 01.05.2009 в 22:12. |
![]() |
#17
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
у меня бы это заняло минуты 3 - 4, но мне и то лень ;) ты прав... |
![]() |
#18
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
J
expert
![]() offline
Опыт:
48,447Активность: |
максимум я ее смог сжать до 130кб, какую-то он туда левую инфу сует=/ у тебя наверно кб 1-10 занимает |
![]() |
#19
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
adic3x
![]() offline
Опыт:
108,439Активность: |
1.5 кб изза того, что надо выделять особую секцию писабельну под данные, что бы туда состояние есп пихать... мне нехватило одного регистра) инче бы меньше 600 кб .ехе весило бы
ADOLF добавил: можно сжимать дальше... сам алгоритм - 75 байт |
![]() |
#20
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|