- Mam dużą liczbę N. Wskażcie proszę najbliższą jej liczbę pierwszą.
Albo nie, wypiszcie WSZYSTKIE liczby pierwsze ograniczone z góry przez N.
Ci którzy posłużą się sitem Eratostenesa biegną zażyczyć sobie bardzo dużego dostępu do pamięci, w którym zamieszczą wszystkie liczby nie większe niż N.
Osoby posługujące sie obliczeniami szykują sobie szybkie procesory, by sprawdzać pierwszość kolejnych liczb N minus k, gdzie k są kolejnymi liczbami naturalnymi. Sprawdzają też schematy występowania liczb złożonych dla przespieszenia obliczeń.
- A ty, który siedzisz w systemach niedziesiatkowych? Jak sobie poradzisz?
Mogę skorzystać z początkowych liczb pierwszych? Z ich iloczynu? W takim razie sklecę sobie liczbę gładką najbliższą N z iloczynu kolejnych liczb pierwszych i jeszcze jednej, przybliżającej N. A potem odwrócę sito Eratostenesa do tych wartości, szukajac liczb p-kwadrat gładkich, gdzie p będzie mi podstawą systemu, rosnącym, aż znajdę rozkłady kanoniczne wartości najbliższych N.
- Chcę liczby pierwsze, nie rozkłady kanoniczne.
Rozkłady kanoniczne posłużą mi tylko po to, by dla liczby złożonej wskazać, o ile mam skoczyć, by znów trafiać na liczby złożone, oraz ją usunąć jak będzie za gładka. Będę używać zarówno czynnikow pierwszych, jak i ich potęg. To, co zostanie nie wskazane podczas zmian p, okaże się liczbami pierwszymi. Skoki zwiększajace odległość od N będą mi wskazywać liczby coraz mniej złożone, które w końcu staną sie pierwsze.
- Pozostałe iloczyny mogą być złozone. Możesz też pominąć którąś z liczb pierwszych. Zresztą twoje podstawy mogą być liczbami złozonymi.
Początkowo iloczyny będą złozone. Dlatego potrzebuję tej liczby gładkiej. Zapiszę ją jako iloczyny liczb dwucyfrowych przy podstawie p. Zamiast liczyć resztę kolejnych wartości p przez N, najpierw przekonwertuję ją na system o podstawie p, po prostu odejmując od cyfry jedności cyfrę dziesiątek poszczególnych czynników, reszta z dzielenia przez N jest iloczynem cyfr jedności czynników, zmodyfikowanych odległością od N. Wskaże mi to odległość od N, gdzie występuje liczba podzielna przez p, czyli złożona. Dopisując w każdym kroku wartość o kolejnej odległosci p od N pokryję wszystkie wartosci.
Jeśli w początkowej tablicy przy tej odległości jest zapamiętana jakaś wartość większa od p kwadrat, może okazać się albo pierwsza, albo złozona. Kiedy jest podzielna przez p, to p jest kolejną liczbą pierwszą gotową do odłożenia. W przeciwnym razie złozone p uzyska się rozkłądu kanonicznego dla tej odległości. I do tej reszty mogę już nie wracać, pamiętając tylko te wartości wraz z ich odległosciami od N, które podejrzewam o bycie pierwszymi.
- Z początku masz iloczyny liczb jednocyfrowych.
Iloczyn dwu odpowiednio dużych liczb jednocyfrowych jest dwucyfrowy. Kwestia podstawy. Zmiejszać będzie mi się krotność czynników przy okazji.
- Potrzebujesz pamięci na wszystkie liczby pierwsze nie wieksze niż N...
Większej, być moze dwukrotnie - pamiętam też kolejne potęgi liczb pierwszych, zaś sumy tych potęg są mocno ograniczane, wszak suma odwrotności kwadratów jest skończona, co stanowi pułap górny dodatkowej pamięci. Ale tablica rozrasta mi sie w trakcie poszukiwań i sprawdzeń, czy p jest pierwsza, czy nie, kolejne wartości będą mi wypierane przez liczby pierwsze oraz ich potęgi. A potem pozostają tylko skoki na kolejne wielokrotnosci liczb pierwszych, między którymi szukam, gdyż już znam te liczby pierwsze, dla których wartości sa p-kwadrat gładkie.
- A dlaczego nie liczby p-głądkie?
Jeśli mam liczbę dwucyfrową, o której wiem, że nie jest wielokrotnośćią żadnej liczby pierwszej mniejszej niż podstawa, to liczba ta jest pierwsza.
- To moze się udać...
A tablica liczb pierwszych zaczyna się od największych rozpoznanych jako pierwsze. Potem schodzę jakby grzebieniem po kolejnych. Najdłużej potrwa szukanie tych, które się nieco większe niż połowa N, trzecia część N i tak dalej. Potem wystarczy posortować pozostałe, albo działać tak długo, aż same się posortują.
Jeśli chcę znać najbliższą, dopuszczam odległości od N ujemne, by móc sprawdzać także wartości wieksze niż N. I warto mieć lekki zapas odległości.
