Zagadka Liczb Pierwszych

Progdeex napisał(a):

Chodzi Ci o to ,by taką liczbę sprawdzić znając tylko podstawę oraz jej potęgę?

Nie. 2³² - 3 to konkretna liczba. Skoro nie rozumiesz takiego zapisu, to może inaczej. Znajdź mi wszystkie liczby o "wysokim p-wie bycia pierwszą" z przedziału od 4294967193 do 4294967293, przy czym wysokie to dla mnie >> 1/2 (czytaj: znacznie więcej niż 50%). Zrób to bez dzielenia przez 5 (sprawdzenie ostatniego znaku liczby przekonwertowanej do stringa to wielokrotne dzielenie przez 10 a więc i przez 5, z racji wydajności kompletnie odpada).

@pioflor można stworzyć deterministyczny algorytm oparty na Miller-Rabin, jednak on wymaga prawdziwości tejże hipotezy.

Rozumiem,że 2 do potęgi 32 minus 3 to właściwa liczba. Jeśli się temu zapisowi przyjrzeć bliżej to liczba ta będzie zakończona cyfrą 8 minus 3 =5 Tak liczba podzieli się przez 5. Nie wiem czy dobrze piszę. Mogłem się bardzo pomylić, ponieważ liczyłem swoją metodą na kartce papieru.

Co do tych wysokich P więcej jak 50% to według tego co sam programowałem prawdopodobieństwo wskazania liczby maleje wraz jej wielkością. Mogę podać tylko ogólny zbiór z tego przedziału. Takimi prawdopodobieństwami się jeszcze nie zajmowałem.

EDIT

Jednak nie.. Jeszcze raz policzyłem. Wyszło mi ,że liczba zakończy się liczbą 3..hmn

Ale ty rozumiesz że 50% to ma algorytm rand()%2? Jak będę losowo odpowiadał czy liczba jest pierwsza czy nie to uzyskam srednio 50% trafień? Jak twój algorytm działa gorzej to szkoda gadać :P

Człowieku, 32 razy mnożyłeś przez dwa i jeszcze się kopnąłeś (pewnie o jedno mnożenie za mało). Użyj kalkulatora, wyjdzie Ci 4294967296. Od tego odejmij trzy, możesz w pamięci.

A teraz z innej bajki: skąd wiesz, że kończy się na pięć? Używając systemu dziesiętnego jest to banalne, ale i tak się kopnąłeś. Użyj, tak jak komputer, zapisu binarnego i nie dzieląc przez 5 dowiedź, że liczba jest przez pięć podzielna :]

Co do drugiej części Twojej wypowiedzi - zatem zróbmy tak, żeby po odsianiu Twoim algorytmem prawdopodobieństwo znalezienia liczb pierwszych w zbiorze było tylko 4x wyższe od p-wa znalezienia liczb pierwszych w zbiorze nieprzefiltrowanym. Przedział nadal ten sam, od 4294967193 do 4294967293, założenie nadal to samo - nie dzielisz przez 5 (generalnie nie powinieneś przeprowadzać żadnych operacji, które robi sito Eratostenesa, bo tylko będą się dublować). Jedziesz.

ŁF napisał(a):

Człowieku, 32 razy mnożyłeś przez dwa i jeszcze się kopnąłeś (pewnie o jedno mnożenie za mało). Użyj kalkulatora, wyjdzie Ci 4294967296. Od tego odejmij trzy, możesz w pamięci..

Nie mnożyłem. Za długo by to trwało. Samo liczenie na kartce trwa może z 20s. Poprawiłem post. Wyszło,że po odjęciu liczba zakończy się na 3, więc przez 5 się nie podzieli.

Co do drugiej części. Mam Ci wypisać wszystkie liczby z tego przedziału,które nie dzielą się przez 5 bez sprawdzania(dzielenia ich przez5)?

@Progdeex, do czego dążysz? Bo straszne herezje zaczynają się tutaj pojawiać.

Szybko dodajesz ;-)

Wolałbym, żeby niezbędne obliczenia zrobił Twój algorytm, ale jeśli będziesz postępować jego krokami, to czemu nie, możesz podać te liczby + to jak algorytm by doszedł do ich zostawienia albo odsiania. Tylko pamiętaj, komputer działa w systemie binarnym, Ty widzisz że liczba kończy się zerem lub piątką, komputer zamiast 4294967295 trzyma 11111111111111111111111111111111b, tudzież 0xffffffff.

Po raz pierwszy musiałem policzyć tak duże liczby. Może to zaledwie 10 cyfr ale algorytmowi to widocznie nie przeszkadza.
Liczby te nie są podzielne przez 5 i część z nich to pewnie liczby pierwsze. Takie wyniki wypluł algorytm po czasie równym prawie 0:

4294967197
4294967201
4294967203
4294967207
4294967209
4294967213
4294967219
4294967221
4294967227
4294967231
4294967233
4294967237
4294967239
4294967243
4294967249
4294967251
4294967257
4294967261
4294967263
4294967267
4294967269
4294967273
4294967279
4294967281
4294967287
4294967291
4294967293

O to chodziło?

Ale wytłumacz, jak doszedłeś do takich wyników nie dzieląc przez pięć, przecież to o to chodziło. To nie jest "zaledwie 10 cyfr"!!! To 32 cyfry w systemie binarnym!!! Człowieku, przecież nie będziesz tego na kartce liczyć, tylko będzie to realizować komputer. A on kuźwa liczy BINARNIE. Więc skąd wiesz, że 11111111111111111111111110101111b kończy się, albo się nie kończy cyfrą pięć bez dzielenia przez pięć. Bo wypisać jakieś liczby jedna po drugiej i to znacznie większe niż te to ja sam umiem.
Poza tym odsiałeś 60% liczb (z każdej dziesiątki wszystkie parzyste i jedną piątkę), żeby p-wo znalezienia liczby pierwszej w takim zbiorze wzrosło czterokrotnie, to musiałbyś odsiać 75% liczb. Mniejsza z tym. Cały czas usiłujemy Ci udowodnić, że żeby odsiać te liczby to i tak musisz wykonać operacje, które były by użyte w najpospolitszej wersji sita Eratostenesa, ale to jak grochem o ścianę. Sugerowałem, żebyś swoje pomysły zweryfikował robiąc implementację kilku algorytmów i porównując ich wydajność ze swoim pomysłem, a na koniec żebyś wyciągnął wnioski samodzielnie, ale zignorowałeś to. Prosiłem o "podanie tych liczby + to jak algorytm by doszedł do ich zostawienia albo odsiania", drugą część zdania zignorowałeś.
Wniosek sam się nasuwa.

To jest trochę inaczej. Z pewnych dziesiątek zostaje tylko 4 liczby czyli 60 % odpadło. Z innej dziesiątki zostają tylko 2 liczby czyli 80 % odpada. Z całej setki odpadło około 70% liczb.

Pomijając, że słaby troll

generuje kolejne liczby naturalne pomijając te podzielne przez 2,3,5. Bez korzystania z dzielenia.

int a[8] = {6, 4, 2, 4, 2, 4, 6, 2};
for(int v = 1, i = 0;; v += a[i++ & 0x7])
    std::cout << v << '\n';

tysięczna wypisana liczba to 3749

Liczby pierwsze:
(n*n) - 79n + 1601
dla n od 0 do 79.

Kiedyś myślałem,że przy szukaniu liczby pierwszej należy posługiwać się wszystkimi liczbami nieparzystymi oprócz tych,które kończą się na 5.
Trochę pokombinowałem i nastała wreszcie nadzieja. Można omijać liczby nieparzyste tylko w określonych miejscach. Miejsca te wyznaczają liczby,których suma wszystkich cyfr nie jest równa 3|6|9. np. liczba 12 591 suma cyfr to:18 1+8=9 Ta liczba nie jest liczbą pierwszą. Takie liczenie sumy cyfr istnieje w numerologi i tutaj właśnie takie coś zastosowałem.

Prawie taką samą regułę zastosowałem do sprawdzenia jaką ostatnią cyfrę będzie mieć liczba np. 2^126753 -5 czyli (ostatnia 8-5=3) nie wiem jaki wzór istnieje w matematyce na policzenie tego, ale ja to robię właśnie inaczej i pewnie łatwiej :) Przypadkowo jeszcze odkryłem jaką sumę cyfr będzie mieć ta liczba. (2-5=7) To sugeruje,że ta liczba może być liczbą pierwszą.

Do obliczenia dowolnej liczby nieparzystej,która może być liczbą pierwszą stosuję takie wzory:

n - taki wyznacznik dla pewnego zbioru liczb (zb)
zb - zbiór ośmiu liczb pierwszych [11,13,17,19,23,29,31,37] n = od 1 do 8 i wyznacza,którą liczbę pobrać ze zbioru zb
dla n=1 zb=11 dla n=5 zb=23

Najpierw oblicza się n:
n=l-(8*[l/8]) dla n=0->n=8

Potem Liczbę Nieparzystą:
l2=((l-n)/8)*30+zb(n) l-dowolna liczba np. dla l=1000--> l2=3757
Uproszczenie: l2=[l/8]*30+zb(n) dla l=1 l2=11 dla l=2 l2=13 itd.

Kwadratowe nawiasy oznaczają,że dzielimy bez reszty.

Takie rozwiązanie oznacza,że nie trzeba deklarować sporego miejsca na tablicę jak to ma miejsce w sicie,bo jest ona dostępna od razu, a wielkie nieparzyste liczby generować można prawie natychmiast bez konieczności użycia pętli.

W wolnych chwilach ciągle przy tym dłubię i może kiedyś coś jeszcze wymyślę.

@Progdeex, wreszcie odkryłeś zasadę podzielności przez 3, z tym że aby sprawdzić tą podzielność przez 3 musisz co najmniej floor(log10(N)) razy podzielić przez 10 (np dla liczby 12 591 - 4 razy po czym 4 dodawania, znowu dzielenie i znowu dodawanie, po czym dwa ifa), co na 300% procent jest dłuższym działaniem niż zwykła pojedyncza reszta z dzielenia przez 3.

To są jakieś brednie.

Takie liczenie sumy cyfr istnieje w numerologi i tutaj właśnie takie coś zastosowałem.

Terminologia mówi sama za siebie:
https://pl.wikipedia.org/wiki/Numerologia

Wzory działają dobrze dla liczb, które mieszczą się jeszcze w rejestrach :D