XGM Forum
Сайт - Статьи - Проекты - Ресурсы - Блоги

Форуме в режиме ТОЛЬКО ЧТЕНИЕ. Вы можете задать вопросы в Q/A на сайте, либо создать свой проект или ресурс.
Вернуться   XGM Forum > Общение> Трактир
Ник
Пароль
Войти через VK в один клик
Сайт использует только имя.

Ответ
 
Light or Dark

offline
Опыт: 7,275
Активность:
Оптимизация задачи
Помогите пожалуйста!нужно решить задачу нахождение суммы простых делителей.ограничение по времени 2 секунды.число вводится до 10 в 9 степени.
я решил так(язык pascal):
Код:
program crazy_teacher;
var
        ch,sum,i : integer;
begin
readln(ch);
        ch:=abs(ch);
        sum:= 0;
        for i:=2 to ch do
        begin
                if (ch mod i)=0 then begin
                   inc(sum, i);
                   while (ch mod i)=0 do ch:=ch div i
                end;
        end;
        writeln(sum);
end;

но вот проблема-не проходит по времени(>2 секунд)...пожалуйста помогите,что надо сделать!

Light or Dark добавил:
так что,никто не поможет????(((((((((((

Light or Dark добавил:
ну плиииз!помогите!
Старый 01.05.2009, 17:15
MF
Что-то вокруг не так
offline
Опыт: 26,594
Активность:
Light or Dark я не думаю что ты вообще находишь простые делители, так как ты просто убеждаешься что число делится на i, но оно не обяз простое.
Старый 01.05.2009, 19:03
J
expert
offline
Опыт: 48,447
Активность:
Код:
#include <iostream>
using namespace std;

int SumSimNum(int InNumber)
{
    int * SimNum = new int[100];
    if (SimNum == NULL)
        return 0;
    int result = 0;
    int CountNum = 0;
    for(int i = 2; i <= (InNumber/2); i++)
      if ((InNumber%i) == 0)
      {
          bool b = true;
          for(int a = 0; a < CountNum; a++)
            if ((i%SimNum[a]) == 0)
            {
                b = false;
                break;
            }
          if (b)
          {
              result+=i;
              SimNum[CountNum] = i;
              CountNum++;
          }
    }
    delete[] SimNum;
    return result;
}

int main()
{
    while(true)
    {
        int Number = 0;
        cin >> Number;
        cout << SumSimNum(Number) << endl;
    }
}

Отредактировано J, 02.05.2009 в 03:08.
Старый 01.05.2009, 19:11
MF
Что-то вокруг не так
offline
Опыт: 26,594
Активность:
Старый 01.05.2009, 19:11
J
expert
offline
Опыт: 48,447
Активность:
... это бы точно работало бы если мы на простые числа проверяли все числа, а не только делаители, а раз я проверяю только делители то я неуверен, ну нихачу просто думать
Старый 01.05.2009, 19:16
MF
Что-то вокруг не так
offline
Опыт: 26,594
Активность:
J по идее вполне норм, ускорение процесса будет налицо. Если сначала проверять, что число простое, а потом делитель ли, то итераций будет больше. А так вроде норм.
Старый 01.05.2009, 19:22
Light or Dark

offline
Опыт: 7,275
Активность:
у меня все верно(ищет моя прога делители)....спросил у зав. кафедры-она говорит правильно,но надо идти до round(sqrt(ch)) (первый фор).
но у меня это не работает(((
Старый 01.05.2009, 19:34
J
expert
offline
Опыт: 48,447
Активность:
Цитата:
ограничение по времени 2 секунды
аверно это не возможно, ну покрайне мере 10^9, за такое короткое время не прощитать
Старый 01.05.2009, 19:35
MF
Что-то вокруг не так
offline
Опыт: 26,594
Активность:
Light or Dark
Не правильно, если введешь ch = 4 то при i = 4 условие сработает и 4 приплюсуется, а оно как бэ не простое число.

MF добавил:
Хотя... наверное я не прошарил, извинтиляюсь.
Старый 01.05.2009, 20:16
adic3x

offline
Опыт: 108,439
Активность:
» asm
Код:
;; ebp = input
    mov    _temp,  esp
    mov    edi,    01h    ;; edi = temp
    mov    esi,    ebp
    mov    ebx,    edi    ;; ebx = result
    shr    esi,    01h    ;; esi = limit
    _l_00:
    inc    edi
    cmp    edi,    esi
    jg     _l_end
    _l_02:
    mov    eax,    ebp
    xor    edx,    edx
    div    edi
    test   edx,    edx
    jnz    _l_00
    mov    esp,    edi
    mov    ecx,    01h
    shr    esp,    01h
    inc    esp
    _l_03:
    inc    ecx
    cmp    esp,    ecx
    je     _l_add
    mov    eax,    edi
    xor    edx,    edx
    div    ecx
    test    edx,   edx
    jnz     _l_03
    jmp     _l_00
    _l_add:
    add    ebx,    edi
    jmp    _l_00
    _l_end:
    mov    esp,    _temp


ну грубо говоря я все загнал в регистры... но 0ffffffffh считает чувствительно долго (+ не факт что правильно)

ADOLF добавил:
на 15 - сумма 9 (1,3,5) вестимо
на 16 - сумма 3 (1,2)

ADOLF добавил:
10000000h (там чуть больше) - около четырех сек
Старый 01.05.2009, 21:05
J
expert
offline
Опыт: 48,447
Активность:
а, нужно ведь сумма а не список, чуть подправил код

J добавил:
ADOLF мой тоже 0x10000000 делает около четырех сек =p
Старый 01.05.2009, 21:20
adic3x

offline
Опыт: 108,439
Активность:
J, у тебя какой проц ?) и прогони какое то конкретное число - результаты сравним...
Старый 01.05.2009, 21:31
J
expert
offline
Опыт: 48,447
Активность:
2,4 гГр.

J добавил:
но это толкьо для 0x10000000 выполняется так быстро, чем больше список постых чисел тем будет дольше

PS
1 это не простое число

J добавил:
PPS
я вкрутил таймер, он оЧеНь точный, потому лучше отклчюить все что тормозит
Прикрепленные файлы
Тип файла: rar prog.rar (64.0 Кбайт, 11 просмотров )
Старый 01.05.2009, 21:51
adic3x

offline
Опыт: 108,439
Активность:
1 не простое? лол) ну там всеравно, либо 0 либо 1 писать в регистр) только таймер я не прикручу) сейчас резулты сравню

// атлон 2к, 1.666

ADOLF добавил:
как ни странно но у мну результат равен +1 к твоему (ну я понял да 1 надо выпилить в начале)
Старый 01.05.2009, 21:56
J
expert
offline
Опыт: 48,447
Активность:
ADOLF простое число нельзя представить в виде множителей простых чисел
1 = 1*1
получается 1 не простое число
почтиай вики и посмотри списки простых чисел, там нигде нету еденицы
Старый 01.05.2009, 21:56
adic3x

offline
Опыт: 108,439
Активность:
10000002h - 3.7 сек у тебя, сейчас себя проверю...

ADOLF добавил:
так, к своей тулзу прикручивать таймер мне влом, твою из под оли запускать тоже...)
Старый 01.05.2009, 22:03
J
expert
offline
Опыт: 48,447
Активность:
=) вот чем плох асм) а мне всеволишь потребовалось перенести пару файликов из своей старой игры и добавить пару строчек, что заняло полторы минуты)

Отредактировано J, 01.05.2009 в 22:12.
Старый 01.05.2009, 22:07
adic3x

offline
Опыт: 108,439
Активность:
у меня бы это заняло минуты 3 - 4, но мне и то лень ;) ты прав...
Старый 01.05.2009, 22:16
J
expert
offline
Опыт: 48,447
Активность:
максимум я ее смог сжать до 130кб, какую-то он туда левую инфу сует=/ у тебя наверно кб 1-10 занимает
Старый 01.05.2009, 22:22
adic3x

offline
Опыт: 108,439
Активность:
1.5 кб изза того, что надо выделять особую секцию писабельну под данные, что бы туда состояние есп пихать... мне нехватило одного регистра) инче бы меньше 600 кб .ехе весило бы

ADOLF добавил:
можно сжимать дальше... сам алгоритм - 75 байт
Старый 01.05.2009, 22:36
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы можете скачивать файлы

BB-коды Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход



Часовой пояс GMT +3, время: 10:23.