Премини към съдържанието
boy1

Оптимизация на алгоритъм за намиране на делителите на число

Препоръчан отговор


Здравейте! Опитвам се да намеря всички делители на дадено число, но проблемът ми е, че се налага да използвам число с 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;                  }

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

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

Редактирано от 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 със стъпка две

  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Привет !

 

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

 

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 или повече числа, запазени в тази памет, и генерирането им може и да отнеме някакво време, което може и да доста голямо за голям набор от множители. В случая по-полезни ще са Ви самите намерени прости множители в тази форма.

 

Поздрави !

  • Харесва ми 3

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

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

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

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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)

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

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

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

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

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

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

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

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

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

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

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

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

 

Поздрави !

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

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. :)

Редактирано от boy1 (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

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

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

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

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

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

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

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

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

 

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

Само една забележка: след като провериш дали се дели на две и се дели точно нататък числото става 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 

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

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

  • Разглеждащи това в момента   0 потребители

    Няма регистрирани потребители разглеждащи тази страница.

  • Подобни теми

    • от Chris Panov
      Здравейте,
      В момента имам сериозен проблем със взимането на броят на елементи в даден вектор.
      vec.size(); и  
      sizeof(vec) / sizeof(vec[0]); не работят. Програмата те пита за брой ключове за даден тест, въвеждаш ключовете, после въвеждаш и отговорите, които са били дадени, и програмата ги сравнява и в зависимост от това колко верни отговори имаш ти дава точки. Ключовете и дадените отговори са тип char. ("A", "B", "C" etc.)
      Ето го и кода, като повечето съм го направил на коментар за да си тествам само функцията която извежда броя на елементите.
      #include "stdafx.h" #include <iostream> #include <vector> #define CONSOLE_LOG(x) std::cout << x; std::vector<char> keys = {'A', 'B', 'C', 'D', 'E'}; std::vector<char> studentAnswers; int n, points = 0; char key, answer; template <typename T> T vecSize(std::vector<T>& vec) { T size = vec.size(); return size; } /* template <typename T1> void enterKeys(std::vector<T1>& k) { CONSOLE_LOG("Please enter the number of keys: "); std::cin >> n; for (int i = 0, counter = 1; i < n, counter <= n; i++, counter++) { CONSOLE_LOG("Key " << counter << ": "); std::cin >> key; k.emplace_back(key); } } template <typename T2> void enterAnswers(std::vector<T2>& stAns) { for (int i = 0, counter = 1; i < n, counter <= n; i++, counter++) { CONSOLE_LOG("Answer " << counter << ": "); std::cin >> answer; stAns.emplace_back(answer); } } template <typename T3> void getGrade(std::vector<T3>& x, std::vector<T3>& y) { for (int i = 0; i < n; i++) { if (x[i] == y[i]) { points++; } } CONSOLE_LOG("Points: " << points); } */ int main() { /* enterKeys(keys); enterAnswers(studentAnswers); getGrade(studentAnswers, keys); */ std::cout << keys.size() << std::endl; std::cout << vecSize(keys) << std::endl; std::cin.get(); std::cin.get(); std::cin.get(); return 0; } Опитах всевъзможни начини, и пак не става. Идеята е да заместя n променливата със броя на елементите от вектора. Програмата върви по един и същи начин, защото все пак в n променливата запазваме големината на вектора, но бих искал да си го направя с функция.
      Както виждате на края на програмата си извеждам тестове. Първият, който си е по конвенционалният метод си работи сам по себе си, но пък във for цикъл не бачка.
      А вторият е функцията която съм направил. Проблемът е че ми извежда непознат символ - "�"
      Проблемът е че типът на елементите във вектора е char, защото като го направих с int тип си работеше както трябва.
      Бих бил изключително благодарен ако някой може да ме насочи и да ми бутне едно рамо :)
    • от Goshko
      Да се напише програма, която създава структура "Book" като имате следните полета - Title(заглавието на книгата), Автор(Author), Цена(Price) и уникален номер на книгата(ISBN-num). Да се ваведе цяло число n и след него n на брой данни за ученика. Да се изведе на монитора данните за книгата с цена по-висока от предварително зададена.
    • от Нели Николова
      Здравейте, имам две готови задачи, но не мога да ги компилирам. Дали може да ги проверите?
      зад.1 Да се състави програма, която да сортира едномерен масив от цели числа тип short  с име X състоящ се от 19 елемента. Сортирането да се извърши във възходящ ред чрез метода пряка селекция.
      #include <iostream>
      using namespace std;
      void sortAsc(short[]);
      int main() {
          short x[] = {123,13,23,31,1,55,36,17,8,9,10,11,6,12,14,15,16,35,184,19};
           
          sortAsc(x);
          
          return 0;
      }
      void sortAsc(short x[]){
          for(short i = 0; i < 19 ; i++) {
              for(short j = i; j < 19; j++) {
                  if(x[j] < x) {
                      swap(x[j], x);
                  }
              }    
          }
          
          for(int i=0; i<19; i++)
          {
              cout << x << endl;
          }
      }
      зад. 2 Да се състави програма,която реализира динамичен стек от реални числа тип float. Стекът да се преобразува в два нови стека, един стек P за четните и един стек O за нечетните числа от стек едно. Стековете да се извеждат на екрана.
      int main() {
          stack<float>numbers;
          stack<float>p;
          stack<float>o;
          
          for(short i = 1; i <= 200; i++) {
              numbers.push(i);
          }  
          
          numbers.push(200.64);
          numbers.push(203.34);
          
          while(!numbers.empty()) {
              int number = numbers.top();
              
              if (number % 2 == 0) {
                  p.push(number);
              } else {
                  o.push(number);
              }
              numbers.pop();
          }
          
          cout << "EVEN NUMBERS:" << endl;
          
          while(!p.empty()) {
              cout << p.top() << endl;
              p.pop();
          }
          
          cout << "ODD NUMBERS:" << endl;
          
          while(!o.empty()) {
              cout << o.top() << endl;
              o.pop();
          }
          
      }
      Много Ви благодаря :)
       
    • от Georgi Kirchev
      Здравейте имам да предам курсова работа утре ,но не мога да я реша , ще бъда изключително благодарен ако може някой да ми помогне.

      Дефинирайте клас Телевизор, който да е родител на клас Самсунг и клас Сони. Клас Телевизор да има цена и брой продадени за година в сектор private. Класовете Самсунг и Сони да имат в сектор public функции за определяне на общата сума от продажби за година (цена * брой продадени за година). Всички класове да имат конструктори по подразбиране.
       
      Благодаря предварително !
    • от Магдаленаг
      If smb has time to spare please I'd would be very greatful :))
      Дадена е следната класификация:
                                      __________             
                            _______|__________|
      Медицина-|   
                           |          __________             
                           |________|__________|                
      Класификацията да се продължи поне на още две нива. Да се състави йерархия от класове, отразяваща класификацията. Да се декларират съответните класове.
      Да се дефинира виртуална функция, която извежда характеристиките на обект от всеки клас на йерархията. Във функцията main да се изгради масив от обекти от произволни класове в йерархията. Да се разработи функция, която обхожда масива и извежда информация за признаците на включените в него обекти.
      Декларациите на всеки клас от йерархията да бъдат оформени в отделни заглавни (.h) файлове. Дефинициите на всеки клас и функцията “main” да бъдат оформени в отделни модули (.cpp файлове).  Във всички файлове, съдържащи дефинициите на класовете и функцията “main”, чрез директивата #include да се включат съответните заглавни файлове, съдържащи декларациите на класовете. Да се създаде проект, състоящ се от създадените модули.
      Обяснителната записка съдържа заданието, пълно описание на декларираните класове, алгоритми и листинги на модулите.
       
  • Дарение

×

Информация

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