Matcher

Teraz pytanie: Czy da się to jeszcze bardziej zoptymalizować?

Thikim napisz jak przebiega algorytm z tą "4" Astro wytłumaczę to na tablicy 2-wymiarowej. Przykładowa tablica wygenerowana na podstawie (x*30)+y gdzie y = (11,13,17,19,23,29,31,37), x = numer wiersza. 0 (11,13,17,19,23,29,31,37) 1 (41,43,47,49,53,59,61,67) 2 (71,73,77,79,83,89,91,97) 11=(0*30)+11; Według tej tablicy liczba na miejscu pierwszym to 11, na miejscu 12 - 49, na miejscu 24 - 97 Jeśli tablica jest nieskończona to liczba na miejscu 47 846 590 jest równa 179 424 719 I według logiki tablicy nie musisz nigdzie zapisywać, bo masz ją dostępną natychmiast.

Astro algorytm je znajduje tylko TY nie wiesz które to są Po co mi tablica 1mln liczb pierwszych... Do generowania KOLEJNYCH liczb pierwszych wystarczy mi tylko 8 liczb pierwszych. Jeśli zaczynam generowanie od pewnej liczby L to sprawdzę czy kończy się ona cyfrą (1,3,7,9) i sumą cyfr (1,2,4,5,7,8). Potem wystarczy policzyć gdzie ona się znajduje i dodawać do niej następne liczby oraz dzielić ją przez poprzednie liczby wyrażone wzorem. Przykładowo Liczba 179 424 719 podzielona przez 30 da wynik 5980823,96667 Jeśli część całkowitą 5980823 pomnożymy przez 30 to otrzymamy 179 424 690 czyli jest to liczba o 29 mniejsza od 179 424 719. 29 to jedna z liczb pierwszych początkowych i jest ona 6-sta z nich. Liczba 6 to ważna informacja. I teraz liczymy,że Liczba 179 424 719 znajduje się DOKŁADNIE na miejscu o numerze (5980823*8)+6 = 47 846 590 Nie jest to numer liczby pierwszej, tylko liczby ze zbioru wyrażonego wzorem (x*30)+y, a zbiór jest nieskończony. W RSA szyfrowanie skupia się na iloczynie liczb pierwszych. NP. (LP1 * LP2) = L Wnioskuję ,że liczby LP1, LP2, oraz L należą do zbioru wyrażonego wzorem (x*30)+y szkoda,że matematykiem nie jest, bo może opisałbym lepiej te zależności.

Thikim tak jak dla 10mln tak samo i dla 100mln, i do nieskończoności wzór (x*30)+y będzie prawdziwy Zauważ jeszcze,że liczbę 179 424 719 możesz wygenerować poniżej sekundy stosując tylko wzór, lecz jeśli wygenerujesz dalsze liczby, to nie będziesz wiedział czy są one liczbami pierwszymi na 100%. W tym cała zabawa Należy to tak obejść, by nie bawić się w sprawdzanie.. Ale to chyba nie wykonalne. Dobrze zrobiłeś,że porównałeś wydajność takiego algorytmu z "klasycznym". Czy w tym algorytmie generowałeś tylko liczby pierwsze? Jeśli tak to w jaki sposób? Ja bym każdą kolejną liczbę opisaną wzorem (x*30)+y dzielił przez liczby od najmniejszej opisanej tym samym wzorem do liczby najwyższej nie większej od dzielonej liczby,lub nie wyższej od jej pierwiastka. Czyli np. liczba 127 zostanie podzielona za każdym razem przez liczby (11,13,17,19..itd) Jeśli nie podzieli się całkowicie, to jest liczbą pierwszą

Bo dodając 6 omijasz liczby, których sprawdzać nie trzeba.. Popatrz na pierwsze 1000 liczb pierwszych i przelicz sumę cyfr każdej z nich. Nigdy nie wyjdzie ani 3 ani 6 ani 9.. Licząc 2,4,2,4, 6,2,6,4 omijasz właśnie takie liczby.. Dzięki temu sprawdzasz sporo mniej liczb nieparzystych niż byłeś nauczony do tej pory

W ten sposób naliczasz niepotrzebnie więcej liczb.. Po co sprawdzać liczbę 21 i 27 skoro dzieli się na 3?? Liczby z sumą cyfr 3,6,9 nie powinny być sprawdzane. Na każde 30 liczb sprawdzasz tylko max 8, a nie 12 Ciąg 13,17,19,23,29,31,37,41 jest najbardziej zoptymalizowany.

Zaczynasz od 11.. czyli jedziesz:| 2,4,2,4,6,2,6,4 |. Tak można liczyć od samego początku, ale jakbyś chciał liczyć od pewnej liczy np. 211 543 873 453 to będziesz mieć problem co do niej dodać?? masz wtedy 8 kombinacji do sprawdzenia.. Żeby nie sprawdzać każdej możliwości z osobna dzielisz liczbę przez 30. W tym przypadku wynik wynosi 7051462448 i 13/30. 13 to liczba,która została dodana do X*30 --> (X*30)+13 Czyli dalej generując liczby dodajesz kolejno 17,19,23.. itd Inne rozwiązanie to sprawdzenie,która to liczba z kolei. Pierwsza liczba to zawsze 11, druga 13, trzecia 17, Setna 379 A liczba 211 543 873 453 jest na miejscu o numerze : 56 411 699 586.

Dokładnie stało się to 2 lata temu.. Teraz musiałbym przebić się przez stertę gratów i znaleźć zeszyt, gdzie wzór powstał z killu pobazgranych kartek. Pamiętam ,że chodziło dokładnie o liczbę 6. Potem powstał ciąg 11,13,15,17,19,23,25,27,29,31,35,37 itd.. Następnie wykasowałem wszystkie liczby z końcówką 5 i tak to powstało. TAK To jest zysk obliczeniowy Bo liczby spełniają warunki: Suma cyfr(1,2,4,5,7,8) oraz Ostatnia cyfra(1,3,7,9)

90+29=119 - Nie tędy droga.. To działa odwrotnie. Jak masz pewność,że liczba jest pierwsza to wtedy tak możesz rozłożyć. Ale mając za X liczby losowe masz tylko pewne prawdopodobieństwo ,że trafisz w liczbę pierwszą. w przedziale 100-200 takich liczb może być max 24-28% ,więc dużo szukać nie trzeba.

Dodam jeszcze taką ciekawostkę: Przy szukaniu liczb pierwszych można posiłkować się sumą wszystkich cyfr danej liczby. Liczba pierwsza posiada sumę cyfr zawsze równą 1,2,4,5,7,8. więc wystarczy szukać właśnie takich liczb. W dodatku każdą liczbę pierwszą można opisać w sposób (x * 30) +y ,gdzie y to jedna z liczb pierwszych (11,13,17,19,23,29,31,37). Np. liczba 43 = ( 1 * 30 )+ 13 a liczba 2469757 = ( 82324 * 30 )+ 37. Jeśli takie liczby wpisze się w tablicę dwu-wymiarową to liczba x będzie obrazować numer wiersza w tablicy , a liczba y numer kolumny. Dziwnie to wygląda,ale i tak jest bardzo ciekawe. Można pomyśleć,że liczby pierwsze są jakoś uporządkowane i mają swoje miejsce,które można szybko odszukać.. hmn