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

Zadanie Faktoryzacja Wielu Liczb

VPS Starter Arubacloud
0 głosów
222 wizyt
pytanie zadane 7 stycznia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Natknąłem się na takie zadanie: https://szkopul.edu.pl/problemset/problem/XyCljy62BB7HCqYvJNuOyERj/site/?key=statement

Wyczytałem gdzieś, że żeby mieć szybciej niz O(t * sqrt(a_i)), trzeba sitem znalezc wszystkie liczby pierwsze do pierwiastka, i właśnie nie kumam co dalej. Powiedzmy, że np mamy liczbe x = 20. i liczby pierwsze do pierwiastka to 2,3 i jak znaleźć liczby pierwsze 2 * 2 * 5?

1 odpowiedź

0 głosów
odpowiedź 7 stycznia 2023 przez polandonion Mądrala (6,970 p.)

Rozważmy Twój przykład liczby 20. Tak jak podałeś (poprawnie), liczby pierwsze do pierwiastka z 20 (czyli ok. 4,5) to: 2 oraz 3. Algorytm faktoryzacji wygląda następująco:

faktoryzacja(n):
    w pętli(i = 2, i <= sqrt(n),):
        jeżeli (n mod i == 0):
            n /= i
            wypisz(i)
        else
            i ++
    wypisz(n)

 

Dla liczby 20 program zadziała następująco:

poczatek funkcji

    liczba = 20, i = 2:
        (20 mod 2 == 0) ? TAK, wiec:
            20 = 20 / 2 = 10
            wypisz(2)

    liczba = 10, i = 2:
        (10 mod 2 == 0) ? TAK, wiec:
            10 = 10 / 2 = 5
            wypisz(2)

    liczba = 5, i = 2:
        (5 mod 2 == 0) ? NIE, wiec:
            i = i + 1 = 2 + 1 = 3

    liczba = 5, i = 3:
        (5 mod 3 == 0) ? NIE, więc:
            i = i + 1 = 3 + 1 = 4

    i jest większe od sqrt(n), wiec petla konczy dzialanie

    na koniec wypisz(n, czyli 5)

koniec funkcji, twoj program wypisal: 2 2 5,
czyli poprawny rozklad liczby 20 na czynniki pierwsze,
inaczej dokonał faktoryzacji liczby 20

 

Tutaj implementacja w języku C++:

#include <iostream>

using namespace std;

void fact(int n);

int main() {
    int n;
    cin >> n;

    fact(n);
}

void fact(int n) {
    for (int i = 2; i * i <= n;) {
        if (n % i == 0) {
            n /= i;
            cout << i << ' ';
        }
        else
            i ++;
    }

    cout << n;
}
komentarz 7 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
To ma O(sqrt(n)), z <= 10^6, więc wykona 10^9 operacji, wiec jest zawolne. Da się podobno jakoś szybciej rozkładać wiele liczb z sitem, tylko wlasnie nie ogarniam jak. W sensie ze najpierw znajdujesz wszystkie liczby pierwsze do pierwiastka, tylko nwm co dalej
komentarz 7 stycznia 2023 przez polandonion Mądrala (6,970 p.)
wygeneruj sito do tablicy, po czym wyszukuj binarnie dzielniki.
2
komentarz 7 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Napisalem wsumie bardzo podobne na podstawie tego twojego pierwszego:

1 - Generuje sitem dzielniki do pierwiastka z max a_i (do 10^3). Jest ich 168.

2 - Odpalam ten twoj algorytm tylko na tych 168 liczbach pierwszych.

Przeszło na 100pkt. Czy da się szybciej? nwm, ale to wystarczyło w tym zad

Podobne pytania

0 głosów
0 odpowiedzi 205 wizyt
pytanie zadane 1 września 2022 w C i C++ przez Noizz00 Użytkownik (910 p.)
0 głosów
1 odpowiedź 295 wizyt
pytanie zadane 25 maja 2018 w C i C++ przez Damian Sierocki Użytkownik (800 p.)
0 głosów
0 odpowiedzi 229 wizyt
pytanie zadane 20 stycznia 2018 w SPOJ przez niezalogowany

92,452 zapytań

141,262 odpowiedzi

319,080 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!

...