Здравейте! Опитвам се да намеря всички делители на дадено число, но проблемът ми е, че се налага да използвам число с 15 цифри. Сигурно се досещате, че отнема доста време, ако използваме стандартния начин за търсене, който съм приложил:

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= m/2; i++)          {            if(m%i == 0)               {                cout << i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }

Бих искал да Ви попитам дали има по-оптимален алгоритъм? Търсих в Гугъл, но не успях да намеря нищо :/.

... не съм прочел въпроса правилно, извинявам се за отговора

Редактирано 21 юни 201313 г. от volland (преглед на промените)

Здравейте! Опитвам се да намеря всички делители на дадено число, но проблемът ми е, че се налага да използвам число с 15 цифри. Сигурно се досещате, че отнема доста време, ако използваме стандартния начин за търсене, който съм приложил:

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= m/2; i++)          {            if(m%i == 0)               {                cout << i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }

Бих искал да Ви попитам дали има по-оптимален алгоритъм? Търсих в Гугъл, но не успях да намеря нищо :/.

АМи няма прост начин, иначе RSA базираната криптография щеше да е разбита отдавна. И не е ли по-лесно да търсите простите множители и след това да ги комбинирате. Така ще се налага да смятате само до корен квадратен от числото и можете да започнете от 3 със стъпка две

Привет !

 

Ето и от мен няколко идеи за забързване на написаният алгоритъм:

 

1) Идея за "ловене" на два делителя с една проверка: 

Плюсове: Написаният от колегата boy1 алгоритъм ще цикли до около числото N = m/4.

Минуси: Извеждането на делителите няма да има наредба, а ако искаме такава, трябва да помислим за заделяне на памет + операция за сортиране + извеждане

т.е. ако ги искаме сортирани, ще получим време: O(m/4 + t*log(t) + t), където t е броя намерени делители.

 

Минуса мисля, че може да се разреши с използването на рекурсия и по - точно с обръщение към метода в момента, когато сме извели първия множител и преди да изведем втория. Ще е малко извратена рекурсия, но мисля, че е възможно.

 

Идея: При намиране на делител R на числото m, то числото m/R също е делител. В случая, R <= m/R <= m/2. Това означава, че с нарастване на R, то m/R ще намалява и ще се отдалечава от m/2, което пък води до идеята, цикъла да прави корекция до кое число да бъде изпълняван, като това число е < m/R, вместо m/2.

 

Като пример: С оригиналния алгоритъм, за числото 15 ще се направя 6 цъкъла (от 2 до 7 включително), докато с оптимизацията, те ще са 3 (от 2 до 5, без 5, защото вече е намерен делител още при проверката на 3).

 

2) Идеята за прости множители (Идеята на capnemo) 

Както колегата сподели, може да се опитаме да намерим всички прости множители на числото - това ще гарантира, че цикъла ще извърти до числото sqrt(m), но ще се наложи получените числа да се пазят. Самите делители ще са комбинация от 1, 2 или повече числа, запазени в тази памет, и генерирането им може и да отнеме някакво време, което може и да доста голямо за голям набор от множители. В случая по-полезни ще са Ви самите намерени прости множители в тази форма.

 

Поздрави !

Начин за ускорение на работата на алгоритъма, е и реализирането му чрез използването на няколко нишки, работещи паралелно, които претърсват различни интервали.

Начин за ускорение на работата на алгоритъма, е и реализирането му чрез използването на няколко нишки, работещи паралелно, които претърсват различни интервали.

Това само на пръв поглед изглежда ефективно. И то само ако можем да пуснем всяка нишка на отделно ядро.

Но ако намираме прости множители няма как да стане със спаралеляване. Но за сметка на това операциите ще са по-малко от sqrt(n)/2, където n е числото

1) Идея за "ловене" на два делителя с една проверка: 

Мерси за съвета. Преработих алгоритъма малко и сега наистина се забелязва подобрение в скоростта. Ето това направих водейки се по съветите Ви.

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= sqrt(m); i++)          {            if(m%i == 0)               {                cout << i << " ";                 cout << m/i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }

2) Идеята за прости множители (Идеята на capnemo)

Сега ще опитам да напиша и този алгоритъм. Дано да нямам ядове с намирането на простите множители . И доколкото схванах, после просто комбинирам всеки с всеки нали? Примерно намерил съм 5, 7, 11 и умножовам 5*7, 5*11, 7*11?

Сега ще опитам да напиша и този алгоритъм. Дано да нямам ядове с намирането на простите множители . И доколкото схванах, после просто комбинирам всеки с всеки нали? Примерно намерил съм 5, 7, 11 и умножовам 5*7, 5*11, 7*11?

не само, всички делители на числото ще са:

5,7,11, 5*7, 5*11, 7*11, 5*7*11

П.П. и една забележка: мислите ли че в нормалните типове на езика ще можете да съберете число в 15 цифри? Мисля си че трябва да си потърсите библиотека за работа с големи числа

не само, всички делители на числото ще са:

5,7,11, 5*7, 5*11, 7*11, 5*7*11

П.П. и една забележка: мислите ли че в нормалните типове на езика ще можете да съберете число в 15 цифри? Мисля си че трябва да си потърсите библиотека за работа с големи числа

Мисля, че използвайки long long ще успее да събере такова число.

Все пак колегата е добре да провери и коя версия използва на компютъра си, но при мен лично няма проблеми да се изведе и съхрани число с деветнадесет (19) символа.

Използвам VS 2012 върху 64-bit платформа.

Евентуално полезно инфо: 32-bit , 64-bit

 

Поздрави !

Поразрових се и намерих този алгоритъм:

void List::Deliteli(long long m)      {        int t = 0;        while(m%2 == 0)          {            cout << 2 << " ";            m = m/2;                  }                for(int i = 3; m > 1;)          {            if(m%i > 0) i = i+2; //Ето тук в един момент не става ли 9, което не е просто число?            else              {                cout << i << " ";                m = m/i;              }                }         }

Наистина се забелязва още по-бърза скорост. Мислех си да направя същото и аз, но като видях този алгоритъм забелязах нещо: На първия ред от втория цикъл, в даден момент, числото не става ли 9? А 9 не е просто число. Въпреки това всичко си е нормално.

 

И само да спомена, че съм на 32 битова платформа и ползвам Dev-C++ 4.9.9.2. Иначе и аз нямам проблем с числа до 19 цифри, ако ползвам long long.

Редактирано 24 юни 201313 г. от boy1 (преглед на промените)

Болят ме очите да следя алгоритъма, но идеята е следната

Създаваш си масив в който в началото има само числото две

проверяваш дали числото се дели на две като го делиш и проверяваш резултата докато спре да се дели като ако се дели поне веднъж маркираш две като просто множител

след това правиш while по някаква променлива

дефинираш делителя като 3

проверяваш дали числото се дели на 3 като го делиш и проверяваш резултата докато спре да се дели като ако се дели поне веднъж маркираш 3 като просто множител

увеличаваш делителя с две

проверяваш дали е просто число (дали се дели на числата от масива по-горе) При първото делене се маркира като съставно и се връщаш на горната точка

Ако резултата е по-малък от 3 вдигаш флаг за край на while

 

Ох, стана малко оплетено, но си мисля че това е най-простия и бърз начин  

Само една забележка: след като провериш дали се дели на две и се дели точно нататък числото става n/2

Поразрових се и намерих този алгоритъм:

Наистина се забелязва още по-бърза скорост. Мислех си да направя същото и аз, но като видях този алгоритъм забелязах нещо: На първия ред от втория цикъл, в даден момент, числото не става ли 9? А 9 не е просто число. Въпреки това всичко си е нормално.

 

Алгоритъма е доста хитро написан. За съжаление обаче се влияе от входа - т.е. от стойността на числото m. Ето защо:

- Алгоритъма ще е много бърз, ако m има много на брой, еднакви и малки като стойност прости делители - Пример: за 1024, ще се извършат 10 операции, което е < sqrt(1024) = 32

В този случай множителите ще са 10 броя 2-ки т.е. 2^10. Подобно нещо се случва и за 1000 = 2^3*5^3, което са 6-7 операции. 

- Алгоритъма ще се забави, ако m има малко на брой множители и/или множителите му са големи числа - Пример 34042 

Числото има два делителя 2 и 17021 и съответно алгоритъма прави >8500 операции, докато sqrt(34042) < 185

- Алгоритъма ще е еквивалентен на първият Ви алгоритъм в началото, ако m е просто число. - Пример 47093 - с целия си късмет, това се оказа просто число, което автоматически докара броя операции до 23546 (m/2) 

 

Равносметка: Базирайки се на данните, които получих при опитите, както и кода, който се изпълнява, броя операции е доста сложен да се изчисли - изключително много зависи от входните данни. Но прилагайки наблюденията за числа m, клонящи към безкрайност имаме следните изводи:

1) С увеличаване на m, шанса за среща на прости числа намалява драстично

2) С увеличаване на m, се увеличава шанса да се наложи да се проверяват все повече и повече числа, като прага е някъде около m/2 брой проверки.

3) Алгоритъма дава от добри до много добри резултати за относително малко количество от числа, докато метода за проверка до sqrt(m) е гарантиран да изведе правилен резултат, с гарантиран брой операции ~O(sqrt(m))

 

Според мен, оригиналният алгоритъм ще се представи по-добре за повече на брой проверки и за по-голяма гама от числа.

 

P.S. Не е проблем алгоритъма да "провери" и за 9, въпреки, че то не е просто число. В случая, ние сме преминали вече през 3-ката, което означава, че числото m е делено с 3, докато вече не може да се раздели. Визирайки, че 9 = 3*3 , 27 = 3*3*3, то проверката ще мине през тях, но реално няма да промени резултата в израза m = m/i, защото остатъка от числото няма да се дели без остатък нито на 9, нито на 27 

Редактирано 24 юни 201313 г. от dpk (преглед на промените)