[Algorytmy] Rozklad liczby na czynniki pierwsze - Problem

[hawk26]

Witam.

Mam pewien problem. Potrzebuje napisac program, ktory rozlozy mi szereg liczb rzedu 2^63 na czynniki pierwsze. W zadaniu mam okreslone, ze moge skorzystac z sita Eratostenesa oraz moge zdefiniowac funkcje ktora mi sprawdzi czy dana liczba jest pierwsza.

No i mam problem bo sito do pierwiastka z liczby tego rzedu jest za duze, nawet jak pomine liczby parzyste.
Ma ktos pomysl jak to zrobic??

[Zordon]

niestety algorytm o złożoności pesymistycznej \(\displaystyle{ O(\sqrt{n})}\) jest tutaj za słaby. Poczytaj o faktoryzacji ro Pollarda.

[hawk26]

Nie no napisalem ze to zadanie mam zrobic z pomoca sita(a nie tylko sitem, przeciez nawet bym nie spamietal tak duzego zakresu liczb) i moge jeszcze sprawdzic czy dana liczba jest pierwsza.

Myslalem np. zeby na poczatku sprawdzic czy liczba jest pierwsza, jezeli nie jest to dla jakiegos mniejszego niz pierwiastek zakresu sprawdzic sitem czy ta liczba nie dzieli sie przez jakas. Jezeli nie dzieli sie to bylby to iloczyn jakis dwoch duzych liczb pierwszych. No i wtedy jest problem.

Wydaje mi sie ze da sie to jakos zrobic.

[Xitami]

zdaje mnie mi się, że naiwny algorytm to coś koła kwadransa czy dwu.

[Zordon]

Skąd masz to zadanie i dlaczego akurat chcesz je robić sitem? Napisałem Ci wyżej algorytm, który ma szansę sobie poradzić. Każdy inny korzystający z sita będzie musiał sprawdzać wszystkie liczby pierwsze \(\displaystyle{ \leq 10^9}\) co jest raczej trudne.

[hawk26]

No nie wiem moze wykladowca sie pomylil, albo ja zle przeczytalem.

... d/zad2.pdf

[Zordon]

Ok, na ile znam prowadzącego to nie chodzi mu o bardzo szybki algorytm, tylko o ładnie obiektowo napisany program. Na tym się skup A algorytm to po prostu petla od i=1 do \(\displaystyle{ \sqrt{n}}\).

Aha, i jak będziesz pokazywał program to oczywiście pokaż na przykładach gdzie szybko liczy. Powodzenia

[hawk26]

No ok ale caly czas nie moge wpasc na to jak zapamietywac te liczby w sicie(on sam pisze ze nie da sie tak duzo liczb zapamietac).

[Zordon]

Ja bym zrobił sito dla \(\displaystyle{ \leq 10^6}\) wtedy jak liczba wpadnie już do tego przedziału to masz faktoryzację bardzo szybko. No ale jesli nie ma małych dzielników to i tak będzie kłopot. Tego się w ten sposób nie da obejść.

[hawk26]

Dziwne jest to ze wykladowca pisze ze to da sie zrobic

weź pod uwagę, że nie możesz utworzyć tak dużego sita, więc zastanów się jak ten problem
obejść algorytmicznie

[Afish]

Ale dlaczego uważacie, że nie da się zrobić tak dużego sita? Wystarczy kilka spostrzeżeń z teorii liczb, operacje na bitach i już da się zmieścić w typowej pamięci.

[hawk26]

A moglbys powiedziec czy dac linka jak takie rzeczy sie robi?

[Afish]

Linka żadnego nie mam. Zastanów się, jak działa sito. Masz liczby od 1 do n i jedyne, co musisz o nich wiedzieć, to czy każda z nich jest pierwsza, czy złożona. Zatem nie jest Ci potrzebna tablica intów, booli, czy czegokolwiek - wystarczy jeden bit. Możesz użyć bitseta, możesz używać tablicy intów i odpowiednio poprzez przesunięcia bitowe i maski wyciągać dane. Poza tym warto zauważyć, że od pewnego momentu jedynymi liczbami pierwszymi mogą być te, które dają resztę z dzielenia przez sześć równą \(\displaystyle{ 1 \vee -1}\). Do tego aby stwierdzić, czy liczba jest pierwsza wystarczy sprawdzić dzielniki do pierwiastka z tej liczby. Zatem mając liczby rozmiaru maksymalnie \(\displaystyle{ 2^{63} \approx 10^{18}}\) potrzebujemy dzielników do \(\displaystyle{ 10^9}\), z czego odpada nam \(\displaystyle{ \frac{2}{3}}\) liczb, więc zostaje około \(\displaystyle{ \frac{2}{3} \cdot 10^9}\) bitów, co oznacza \(\displaystyle{ \frac{1}{12} \cdot 10^{9} \approx 10^8}\) bajtów, co już spokojnie wejdzie do pamięci.