Znajdowanie najmniejszej liczby z 2^500500 dzielnikami

Question

Natrafilłem na ciekawe zadanie programistyczne, ale niestety program liczy już ponad 20 minut i nie może się doliczyć. Byłbym wdzięczny gdybyście mi pomogli przy optymalizacji kodu (i w ogóle sprawdzili czy jest dobrze :D).

Treść zadania:

Liczba dzielników 120 wynosi 16. W rzeczywistości 120 jest najmniejszą liczbą mającą 16 dzielników. Znajdź najmniejszą liczbę z  2^500500 dzielnikami. Podaj odpowiedź jako modulo 500500507.

Mój kod:

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int dzielniki = 0, liczba = 500000, dzielnik = 1;
    while (dzielniki <= pow(2, 500500)) {
        dzielniki = 0;
        for (; dzielnik <= liczba; dzielnik++) {
            if (liczba % dzielnik == 0)
                dzielniki++;
        }
        if (dzielniki == pow(2, 500500))
            cout <<"Wynik to: " <<  liczba % 500500507 << endl;
        liczba++;
    }
    system("pause");
    return 0;
}

Answer 1

Po pierwsze primo, liczba 2^500500 nie zmieści się w żadnym dostępnym w bibliotece standardowej typie całkowitym (największą liczba jaka się zmieści to (2^64)-1), po drugie, po napisaniu odpowiedniego typu, policzenie wartość tej liczby na statystycznym komputerze raczej nie skończyłoby się przed samozapadnięciem się słońca.

Jest to zadanie na myślenie. Powypisuj sobie na kartce dzielniki kolejnych potęg liczby 2 (np. aż wartość potęgi wyniesie 64), a coś zauważysz :)

Pozdrawiam.

Comments

Taka notka: ułamek sekundy zajęło policzenie tej liczby w Ruby. Być może zastosowana jest jakaś sztuczka pod maską. Choć dla 13^500500 też poszło błyskawicznie.

---

Tak samo Python :D Liczba cyfr: 150666, ogromna liczba.

Answer 2

To jest zadanie czysto matematyczne, nie programistyczne.

Niemniej podstawową optymalizacją byłoby obliczenie `pow(2, 500500)` tylko raz i zapisanie tego w zmiennej. Zakładając, że w ogóle ta funkcja daje jakikolwiek wynik w C++, bo jest to gargantuiczna liczba. W Ruby liczy tę liczbę błyskawicznie na moim starym procku, więc możliwe, że C++ też obsłuży tę liczbę bez żadnych sztuczek. A może potrzebna jest specjalna biblioteka?

Comments

boost.multiprecision da radę, ale pewnie i tak chodzi o algorytm ;)