Snažím sa zistiť, ako môžeme vygenerovať zoznam J najmenších prvočísel v poly-časovom J, na základe skutočnosti, že p "j je menšie alebo rovnaké ako 2j * ln(j) pre j> 2, kde j označuje j-té po sebe nasledujúce prvočíslo. Napríklad p1 = 2 pre j = 1, p2 = 3 pre j = 2. p3 = 5 pre j = 3, p4 = 7 pre j = 4, p5 = 11 pre j = 5 atď. Atď ...
Len nechápem, ako môžem túto skutočnosť využiťvyššie. Kedykoľvek chcem generovať prvočíslo, povedzme 7., skontrolujem to pripojením: 2 (7) * ln (7) = 27,2427 ... Ale toto je úplne zbytočné, ako sa ukázalo. Toto číslo je oveľa väčšie ako posledné generované prvočíslo v mojom poli, čo je logické. Preto sa stále musím uchýliť k hrubej sile kontrolou posledného prvočísla + 1 pre mod0 s každým prvočíslom v mojom poli. Druhou možnosťou je uchýliť sa k už existujúcim algoritmom, ktoré znižujú čas na polynóm.
Môžete mi ukázať, ako môžem túto skutočnosť využiť: p "j <= 2j * ln (j)? Vďaka.
odpovede:
3 pre odpoveď č. 1Aby som ukázal, že dokážem vygenerovať zoznam prvých prvočísiel J v časovom polynóme v J, potrebujem si vypočítať náklady, ktoré generujem.
Ak generujem zoznam kontrolou číseljeden po druhom a zahodenie iných ako prvočíselníkov, sú dve časti nákladov na vytvorenie zoznamu - ako dlho trvá kontrola každého čísla a koľko čísel musím skontrolovať.
Keby boli prvočísla mizne zriedkavé, potom by som nemoholdovoliť si skontrolovať každé číslo od 2. dňa, pretože jednoduché uvedenie všetkých týchto čísel by bolo príliš drahé. Ale ak viem, že jódová premiéra nie je väčšia ako 2j * ln (j), môžem ich aspoň uviesť v polynomiálnom čase.
V skutočnosti, ak musím vygenerovať prvočísla J a jaZačnem tým, že vezmem prvé 2J * ln (J) čísla a ja sa rozhodnem skontrolovať, či je každé číslo prvočíselné, tak, že ho rozdelím každým doteraz nájdeným prvočíslom, nikdy nemám po ruke viac ako J prvočísel, takže nemôžem nakoniec urobia viac ako 2J ^ 2 * ln (J) pokusné oddelenia. To mi nezískalo žiadnu cenu za efektívnosť alebo múdre algoritmy ani ostré hranice výpočtových nákladov, ale nie je to horšie ako polynóm.
2 pre odpoveď č. 2
Možno, čo ťa zakopáva je, že si myslíš, že horná hranica ti dáva metóda priamo generovať j-té prvočíslo alebo prvé prvočísla. Neurobí to, len vám dá limit veľkosti na množine čísel, ktoré musíte skontrolovať pomocou nejakej metódy, ktorú ste už ležali, napr. súdne rozdelenie.
Ak vám dám zoznam n-1 čísiel 2, 3, ..., n a požiadam vás o nájdenie všetkých prvočísel v tomto zozname, môžete to urobiť pomocou skúšobného rozdelenia v čase O (n ^ 2):
- Pre každú dvojicu čísel x a y stačí skontrolovaťči sa x rozdelí rovnomerne na y, a ak áno, preškrtnite y. Tento krok je O (n ^ 2) a vyžaduje O (n) priestor na sledovanie, ktoré čísla boli prečiarknuté.
- Uveďte všetky čísla, ktoré neboli prečiarknuté. Tento krok je O (n).
Všimnite si, že toto nájde všetky prvočísla <= n v O (n ^ 2) pre akýkoľvek kladná hodnota n. Konkrétne, ak nám povieme nejakú hodnotu j, bude to fungovať pre n = RoundDown (2j log j).
Pri n = RoundDown (2j log j) sa tento algoritmus spustív čase O ((2j log j) ^ 2) = O (j ^ 2 log ^ 2 j), čo je polynóm vj, a musí sa mu podariť nájsť aspoň prvé prvočísla j, pretože väzba nám hovorí, že j-prime môže byť nanajvýš RoundDown (2j log j) a do nášho zoznamu vstupov sme zahrnuli každé číslo až do tohto čísla. (Môže to nájsť ešte viac prvočísel, ale v prípade potreby ich môžeme zahodiť v lineárnom čase.)
Cvičenie: Porozmýšľajte o tom, prečo sa môžeme obísť nadol tu.