• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Znajdowanie najmniejszej liczby z 2^500500 dzielnikami

VPS Starter Arubacloud
0 głosów
373 wizyt
pytanie zadane 26 grudnia 2017 w C i C++ przez Przemko Nowicjusz (140 p.)
edycja 26 grudnia 2017 przez Arkadiusz Waluk

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;
}

2 odpowiedzi

+1 głos
odpowiedź 26 grudnia 2017 przez CzikaCarry Szeryf (75,340 p.)
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.
komentarz 26 grudnia 2017 przez Schizohatter Nałogowiec (39,600 p.)
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.
komentarz 26 grudnia 2017 przez SebekChlebek Stary wyjadacz (11,290 p.)
Tak samo Python :D Liczba cyfr: 150666, ogromna liczba.
+1 głos
odpowiedź 26 grudnia 2017 przez Schizohatter Nałogowiec (39,600 p.)

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?

komentarz 26 grudnia 2017 przez niezalogowany
boost.multiprecision da radę, ale pewnie i tak chodzi o algorytm ;)

Podobne pytania

0 głosów
1 odpowiedź 7,114 wizyt
0 głosów
1 odpowiedź 1,368 wizyt
pytanie zadane 28 lutego 2016 w C i C++ przez Madrox24 Początkujący (350 p.)
0 głosów
1 odpowiedź 2,373 wizyt

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...