Skocz do zawartości
Forum Kopalni Wiedzy
KopalniaWiedzy.pl

Liczby pierwsze nie są rozłożone losowo?

Rekomendowane odpowiedzi

Witam, dyskusja zamarła, ale obserwowałem ją i była moim napędem do pisania programu.

Nie wiem czy wyjdzie szybciej, ale mi się skończyły pomysły na przyspieszanie.

Wrzuciłem projekt (w javie) na githuba: https://github.com/marioc8/primeSentinel30.

Udało mi się osiągnąć 10^9 w niecałe 2 sekundy. Jednowątkowo.Wielowątkowo nie umiem, javy uczę się trochę ponad rok.

Nie starałem się wymyślić wzoru, ale i tak trochę czasu mi zajął nawet w takiej formie.

Jest jeszcze wiele bugów do ogarnięcia, ale ogólnie z eclipse program chodzi bez problemu, i można robić benchmarki.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

10^9 to czym jest? :)

Każdy wątek kiedyś umiera.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Skróty myślowe, zakres od 1 do 10^9 przegląda w niecałe 2 sekundy na procku i5, poprawiam.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

I ile liczb pierwszych znajdujesz w tym zakresie?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Dokładnie to jest to zakres od 7 do 1_000_000_020, znajduje w nim 50,847,534 pierwszych.

Wielokrotności 2,3 i 5 są całkowicie pominięte w całym procesie.


Edycje mam wyłączoną, chyba jeszcze nie zapracowałem na nią. W powyższym zakresie znajduje 50,847,536 liczb pierwszych.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Swoją drogą zrób trochę większy zakres. np. do 100 mld.

Przy 2 sek. to ciężko ocenić szybkość.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

:)

zakres do 100 mld. jest dla mnie na razie nie osiągalnym musiałbym pomyśleć o robieniu tablicy int, long albo użyć dysku.

Java pozwala mi na maksymalnie 64_410_000_030 tablicę bajtową, potem jest problem z adresowaniem.

Wyniki dla i5 7600k 3.8 GHz:

64_410_000_030    128.697 s2,701,477,379 liczb pierwszych


poprzedni się nie liczy :P, jeszcze raz:

 

64_410_000_030      128.697 s    2,701,477,379   pierwszych - maksymalna osiągalna wartość tablicy byte w technologii modulo 30 na bitach

50_000_000_010        97.805 s    2,119,654,578   pierwszych

10_000_000_020        17.035 s       455,052,512   pierwszych

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

po przeczytaniu całego topi'cu duzo się nauczyłam, nawet bardzo duzo.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Taśma9 zrób test na swoim procku moim "starym" programem :)

 

Powinno być sporo wolniej :D Ale da mi to odniesienie do Twoich paru sekund :D

 

PS:

wątek może i umarł, ale tylko dlatego, że nie było zbytnio co testować. Mój stary notes ciągle czeka na nowe pomysły i możliwości, a skończyło się na RAMKACH i sposobie ich przedstawienia oraz kilku "dziwnych" pomysłach, które zakończyły się ślepą uliczką...

Oblicza liczby pierwsze max optymalizacja.zip

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

takie mam wyniki bez OC:

 

  78,499   pierwsza to   1000003,   czas:      14s      mój: 0.003s

148,934   pierwsza to   2000003,   czas:      39s      mój: 0.008s

216,818   pierwsza to   3000029,   czas: 1m17s      mój: 0.008s

 

ale jest duże ALE, ponieważ nie mam Windowsów, test robiłem na wine-2.0.2 pod Ubuntu 17.10, tylko taki mam system.

Od czasów możesz odjąć jakieś 5 sekund, przez które wpisywałem numer liczby pierwszej, a po zakończeniu działania programu wciskałem Enter.

Przy dużych liczbach ( 100 milionów ) Wine nie dawało rady, wywalało się.

Już od jakiegoś czasu w planach miałem maszynę wirtualną z darmowym XP, więc chyba po prostu przyspieszę wykonanie zadania, i przeprowadzę ponowne testy ;)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Pewnie dlatego taka rozbieżność, bo u Ciebie operacje są wykonywane na liczbach bitowych, a u mnie na dziesiętnych :D

 

100 mld nawet nie wpisuj, bo program był dawno temu kompilowany i tam ograniczeniem była granica liczby pierwszej 1mln :) Ja uzyskałem wtedy liczbę 500.000 -> 7368787 według tej strony http://liczby_pierwsze.republika.pl/ się zgadza.

Edytowane przez Matcher

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
le jest duże ALE, ponieważ nie mam Windowsów, test robiłem na wine-2.0.2 pod Ubuntu 17.10, tylko taki mam system.

A czego chcesz się uczyć? Dlaczego wine? Nie masz Javy w Ubuntu? Eclipse?

Ubuntu daje wszystko co potrzeba

gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.5) 

 

jajcenty@Detrytus:~/sndbx/cnslapp$ dotnet --version
2.0.0
 
Python też jest. Po co wine? Masz  ulubione IDE?
 
p.s. Pobudzony ruchem tutaj bawię się sitem Atkina. Wydaje się wdzięcznym polem dla wyciskania efektywności z algorytmu.
Edytowane przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jajcenty, maszyna wirtualna mi się przyda żeby sprawdzić jak instalować i uruchamiać programy pisane w Javie, żebym wiedział jak u znajomych którzy mają tylko Windowsy sprawdzić swój program, ale jakiś skrypt. Czysta potrzeba wiedzy :P

Z "C" dałem sobie spokój, dla mnie za trudne.

To co robiłem w "C" w kilka miesięcy w Pythonie zrobiłem w tydzień.

 

dotnet ? hmm, tego nie znam :P

 

Mam Javę a Eclipse to mój ulubiony IDE :)

I wygląda że tak już zostanie.


A dlatego Wine, ponieważ chciałem jakoś zrobić test, a innej możliwości pod Ubuntu nie znam, chyba że Dosbox ;)


p.s.

Mój programik powstawał dosyć długo, koniec końców to jakaś odmiana sita Atkina, ale najpierw było to sito Eratostenesa operujące na kolumnach liczb z końcówką 1,3,7,9, zresztą jeszcze mam kod na pamiątkę :) Ale to właśnie na Eratostenesie zauważyłem że można odznaczać w każdej kolumnie liczbę że nie jest pierwszą bo jest pochodną, a następna pochodna np liczby 3, to 33, czyli indeks 0 + 3 = 3, czyli 3 * 10 + 3, wystarczyło obliczyć punkt początkowy, i dalej to już zwykła pętla dla każdej z czterech kolumn. Nie było łatwo ;)


p.p.s.

Matcher, to znaczy że robisz wszystko w ascii ?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

W programie zadeklarowany był typ zmiennej int long long z tego co pamiętam.

 

Twoja tabelka więc wygląda tak?

 

11 | 13 | 17 | 19

21 | 23 | 27 | 29

 

Jak tutaj można wyznaczyć stałe reguły do wyznaczania LP?

 

Ja robiłem na takiej tabelce:

 

11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 |

41 | 43 | 47 | 49 | 53 | 59 | 61 | 67 |

 

Na dodatek nie trzeba rysować całej tabelki, bo można przenieść się w Każde jedno jej miejsce.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

W mojej tabelce jest stała reguła do wykreślania liczb które nie są liczbami pierwszymi, np znajdujesz indeks [0,1] który ma wartość "0" (czyli 3) to znaczy że to liczba pierwsza, teraz tak,

indeks [3,1] zaznaczasz jako "1" ( czyli 33 ), indeks [6,1] zaznaczasz jako "1" ( czyli 63 ):

 

  1 |   3 |   7 |   9

11 | 13 | 17 | 19

21 | 23 | 27 | 29

31 | 33 | 37 | 39

41 | 43 | 47 | 49

51 | 53 | 57 | 59

61 | 63 | 67 | 69

 

czyli znalazłeś na indeksie 0 liczbę 3, i teraz w pionie w tym słupku dodajesz do indeksu tą liczbę ( 3 ) i skreślasz, i tak do końca zadeklarowanej tabelki, 3, 33, 63, 93, 123, 153, indeks cały czas zwiększasz o 3. Dla innych kolumn zmienia się tylko punkt startowy, dla zerowej kolumny to indeks "2", dla trzeciej kolumny to indeks "27", czyli pierwsza liczba która dzieli się przez "3" w danej kolumnie.

Dla 7 indeks będziesz się zwiększał o 7, dla 11 o 11.


p.s. tylko koniec końców wyszło że liczb pierwszych o 1 do 30 jest Osiem, więc pierwsze skojarzenie to bajt i 8 bitów, wierzę pan od primesievie wpadł na coś bardzo podobnego.


p.p.s a nawet nie osiem liczb pierwszych, tylko przy modulo 30 jest osiem słupków w których mogą być liczby pierwsze.


p.p.p.s ERRATA: dla drugiej kolumny to indeks "2" czyli liczba "27", a dla trzeciej kolumny to indeks "0". sorki, taki mały świerszczyk ;)


4p.s.

Nie odpowiedziałem na pytanie, liczba pierwsza w sicie będzie miała wartość "0" bo nie została skreślona przez żadną poprzednią liczbę.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Tak właśnie jest Osiem słupków i tylko tam znajdują się LP. Ogólnie to można zauważyć, że w tych słupkach są takie 10-tki liczb. np: zakres 10-20 - tutaj mogą być max 4 liczby P. Zakres 30-40 tutaj już tylko max 2 LP. Rozciągnij sobie taką tabelkę do nieskończoności.

 

PS:

Czy dla zadanego zakresu liczb Twój program dzieli tą tabelkę na wiele mniejszych części czy działa na całej tablicy?

 

PS:

Dodałem program ,który przy obliczeniach nie korzysta z żadnej tablicy (Sita). Ogranicza go tylko typ zmiennej Long Long int.

LiczbyPZapis2.zip

Edytowane przez Matcher

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Moja tabelka tak wyglądała, gdy robiłem na sicie Eratostenesa, to było na początek tak dla uproszczenia, łatwiej było znaleźć reguły, które potem ładnie przeniosły się na sito modulo 30.

 

Mój program działa na całej tablicy.


Matcher, ten program który teraz dodałeś w jaki sposób oblicza liczby pierwsze ? Zakładam że nie dodaje liczb 2,3,5 i 7 do wyniku.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Program działa na tej tablicy o ośmiu kolumnach, ale nie posiada jej w pamięci. Jak by to najprościej wyjaśnić:

 

Po kolei program przechodzi przez każdy element tej tablicy [liczbę] i klasycznie dzieli go przez każdy element należący do tej tablicy, dzięki czemu nie potrzeba deklarować w pamięci drugiej tablicy na znalezione liczby pierwsze. Rozciągnij moją tabelkę do wielkiego zakresu i największą liczbę w tej tabelce dziel klasycznie przez elementy tej tabelki zaczynając od jej początku [11]. Jak się nie podzieli to liczba jest pierwsza.

 

Nie ma tutaj żadnego dodawania 2,3,5,7. Tu jest tylko wzór na każdy element [liczbę] tej tabelki.

Edytowane przez Matcher

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Mam wrażenie że będę musiał przestudiować jeszcze raz cały topik i przemyśleć temat ;)

 

Tablica jest dobra dla mniejszych zakresów, ale im dalej w las, tym ciemniej - mniej LP.

Na tym moim programie można by było sprawdzić czy liczba jest pierwsza w zakresie od 1 do liczby z 4 z przodu i następnie 21 zerami,

co już trochę wykracza poza 64bity, co mam zresztą w planach ;) Jeszcze muszę dopisać część zliczającą LP do Long.MAX_VALUE, i tutaj z czasami już może nie być tak wesoło.

 

Wzór na liczby pierwsze to musiało by być coś co adaptuje się do zmieniających się warunków, po co sprawdzać 80 tysięcy liczb w których nie ma LP ?

albo zajmować tym pamięć.

 

Na dzisiaj mi starczy :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

By wypisać liczby pierwsze trzeba omijać liczby złożone. Zobacz sobie mój arkusz kalkulacyjny excel, który pokazuje tzw. Ramki. Każda z nich posiada po osiem liczb złożonych wyróżnionych kolorem. Każda z tych liczb przypada na jedną z ośmiu kolumn. Jeśli dla liczby 11 stworzymy kilka takich ramek to położenie liczb złożonych mających dzielniki z 11 będzie takie samo dla każdej ramki, więc odstępy między nimi są takie same, co pozwala odpowiednio "w locie" działania programu omijać liczby z dzielnikami 11,13,17........ itd.

 

Problem jest w tym,że potrzebna jest tablica z danymi zawierająca przesunięcia dla każdego dzielnika, co będzie zapełniać RAM w nieskończoność. Aktualnie myślę czy można ominąć ten problem jakoś inaczej :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Patrzę na tą tabelkę i chyba wiem o czym mówisz.

Najprostsze rozwiązanie które widzę to robić sito za każdym razem jak znalazłeś nową LP:

 

np znalazłeś 2, robisz sito modulo 2, czyli binarne,

znalazłeś 3, robisz sito modulo 6,

znalazłeś 5, robisz sito modulo 30,

znalazłeś 7, robisz modulo 210 ... itd do nieskończoności, tylko że szybko zabraknie pamięci w komputerze,

bo okaże się że przy 10 LP musisz zrobić sito modulo 6,469,693,230 które jeśli będziesz przechowywać w bitach zajmie ponad 770MB co jeszcze jest do ogarnięcia,

ale przy 11 LP czyli "31" modulo dojdzie do wartości 200,560,490,130 a to już trzymane nawet w formie bitów zajmie przeszło 23GB.

Duży przeskok, ale następny to ponad 860GB, a następny to już ponad 34,5 TB, pod warunkiem że każda liczba to 1 bit.

 

Minusy są takie że:

albo musisz trzymać wtedy bit do każdej liczby, bo jeżeli stworzysz sito dynamicznie to będzie to najprostszy sposób na wyliczenie jaka to liczba,

albo musisz zapamiętywać LP, możesz to robić na zasadzie że poprzednie sito modulo tworzy nowe sito modulo, albo zapamiętywać LP w formie int lub long

 

 

RAM zawsze będzie się zapełniał w nieskończoność, jeśli będziesz liczył nieskończony zakres ;)

 

 

Patrzę na arkusz i tak myślę, gdybyś wiedział jak ominąć ten problem, to byłby to wzór na liczby pierwsze :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Tylko czy ktoś może tą Spiralę analizował głębiej? Na matrycy 2D ułożenie LP wydaje się chaotyczne, choć widać podobne kształty figur..

 

Ciekawy jestem, czy można by było zastosować tu sieć neuronową do nauki takiej planszy 2D, a potem wykorzystać do przewidywania dalszych LP.

 

Jeszcze jedna myśl: LP nie mają dzielników. W tabelce wypełniają tylko puste luki. A gdyby brakło jakiejś liczby, to nie powstałyby kolejne liczby w tabelce. Czyli LP to takie cegiełki, które muszą istnieć. Brak jakiejkolwiek z nich spowodowałoby zanik dalszych liczb złożonych. Powstałyby "dziury", których byłoby coraz więcej i więcej. hmn. ciekawe :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

Tylko czy ktoś może tą Spiralę analizował głębiej?

Możesz się założyć, że tak.  :D

 

Jeśli zajrzysz do polskiej wiki https://pl.wikipedia.org/wiki/Liczba_pierwsza do sekcji "rozmieszczenie" zobaczysz obrazek na który widać dlaczego może się wydawać że istnieje prosta liniowa zależność między numerem liczby pierwszej a liczbą pierwszą. Po pierwsze liczby pierwsze są w postaci:

lp = 2n+1 co definiuje super prostą.

Z tej prostej wywalamy wszystkie liczby np w postaci notprime = 60n znowu prosta i znowu cykl - teraz wrażenie cykliczności już nas nie opuści.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Czyli jak to jest z tą cyklicznością?

 

Na obrazku widać miejsca całkowite puste i również te w większości zapełnione. Nie wiem tylko czemu w tej spirali liczba LP wydaje się stała, choć wiadomo,że im dalej jedziemy tym mniej po drodze znajdziemy.. Co można jeszcze wywnioskować z tego obrazka?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

×
×
  • Dodaj nową pozycję...