Zagadka Liczb Pierwszych

0
Progdeex napisał(a):

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

Nie. 232 - 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).

0

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

0

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

0

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

0

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.

0
Ł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)?

0

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

1

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.

0

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?

2

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.

0

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.

0

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

0

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

0

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ę.

2

@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.

1

To są jakieś brednie.

1

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

0

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1