Szukanie liczb pierwszych

[goofyx]

Mam pytanie w kwestii jak w temacie.
Mając nawet bardzo dużą liczbę całkowitą > 0 nie można by sprawdzać czy jest pierwsza próbując dzielić tą liczbę przez liczby między 2 a 10 ?
Oczywiście wszystkie liczby parzyste > 2 od razu wykluczamy, więc mamy połowę roboty mniej ;)
I wtedy jeśli liczba jest podzielna przez więcej niż 1 liczbę z tego przedziału to nie jest liczbą pierwszą tylko złożoną.

Czy źle myślę? <- moje ulubione stwierdzenie ostatnio ;)

[Troll81]

niw wystarczy :D

np 221 :D

nie podzielisz przez 2 ani przez 3 przez 4 i 5 też nie przez 7 też nie. a przez 13 dasz radę :D

[goofyx]

niw wystarczy :D

np 221 :D

nie podzielisz przez 2 ani przez 3 przez 4 i 5 też nie przez 7 też nie. a przez 13 dasz radę :D

hmm, niby tak ;)

[Troll81]

sorry ale musisz robić pełny test. oczywiście z zadanego przedziału liczbowego z miejsca wywalasz wszystkie liczby kończące się na 2,4,5,6,8,0 bo wiadomo że będą podzielne przez 2 lub 5 :D to pozwala odsiać tak z 60% liczb z danego przedziału.

[Krzysiak]

Tylko sytuacja się komplikuje jak szukasz liczb pierwszych z równań np: 3·2n±1
Jak to masz w PrimeGrid

A tu mas to o czym po części pisałeś z Wikipedii

[goofyx]

Tak wiem widziałem to.

sorry ale musisz robić pełny test. oczywiście z zadanego przedziału liczbowego z miejsca wywalasz wszystkie liczby kończące się na 2,4,5,6,8,0 bo wiadomo że będą podzielne przez 2 lub 5 :D to pozwala odsiać tak z 60% liczb z danego przedziału.

Podobnie jak ze sprawdzeniem czy liczba jest podzielna przez np.: 3 jeśli nie to nie warto sprawdzać czy ta liczba dzieli się przez wielokrotności 3 <- podobnie jest z resztą liczb.
Czytałem gdzieś że wystarczy sprawdzić czy pierwiastek z danej liczby jest liczbą pierwszą oczywiście poczynając kroki o których wcześniej mówiliśmy.
To teoretycznie całkiem niezłe czasy by były nawet przy sprawdzaniu każdej liczby nieparzyste od 3 w górę <- wszystkie kolejne, a nie szukać jakiś tam.

[GRID]

A co zainteresowałeś się szukaniem liczb pierwszych na potrzeby jakiegoś projektu naukowego BOINC ?
Czy tylko tak sobie teoretyzujesz ?
Przyznam żeby przebić największe projekty matematyczne z naszą niską mocą obliczeniową przydał by się jakiś nowy genialny algorytm.

[goofyx]

A co zainteresowałeś się szukaniem liczb pierwszych na potrzeby jakiegoś projektu naukowego BOINC ?
Czy tylko tak sobie teoretyzujesz ?
Przyznam żeby przebić największe projekty matematyczne z naszą niską mocą obliczeniową przydał by się jakiś nowy genialny algorytm.

Jeśli chodzi o szczerość to szukanie liczb pierwszych od zawsze mnie pasjonowało <- nie wiem dlaczego.
Na jakieś tam zaliczenie w technikum napisałem prosty programik (na algorytmy i na matme), który szukał liczb pierwszych od 1 do 2147483647 (czyli w zakresie typu LongInt w delphi).
Genialny algorytm? <- nie znam takiego.
Mój programik brał po kolei liczby z tego zakresu i dzielił przez liczby całkowite od 2 w górę <- nie licząc liczb parzystych większych od 2.
Jeśli jakaś liczba dzieliła się przez więcej niż 2 liczby to był koniec sprawdzania.
Nie było to optymalne, ale nawet szybkie w tym zakresie.

Niedawno czytałem o różnych algorytmach/sposobach na znajdowanie LP (liczb pierwszych).
Teoretycznie mógłby powstać projekt, który sprawdzał by czy podana liczba jest pierwsza, a wynikiem mógłby być czas szukania <- wtedy można by znaleźć najszybszy algorytm dla liczb z danego przedziału wielkości.

Gdyby nie fakt, że pomimo dziesiątek prób nie udało mnie się uruchomić serwera dla projektu boinc (nie znam linucha za dobrze szczególnie od strony linii komend <- robiłem krok po kroku instrukcje z maszyną wirtualną, ale zawsze coś się sypało) to pewnie dla zabawy zająłby się takim projekcikiem.

[Troll81]

zawsze możesz poprosić o pomoc w postawieniu serwa i dać dostep przez SSH :D

[goofyx]

zawsze możesz poprosić o pomoc w postawieniu serwa i dać dostep przez SSH :D

3 osoby w zeszłym roku obiecały pomóc <- ale niestety do tego nie doszło :(
Nie będę ich wymieniał.

[GRID]

Nie martw się - odnajdziemy te liczby.  :p_arr:

[Sebastian M. Bobrecki]

W zasadzie jak na razie są tylko dwie sprawdzone metody poszukiwania dowolnych liczb pierwszych:
1). to faktoryzacja, i tu chodzi o to żeby znajdować dzielniki danej liczby inne niż ona sama i jeden. Mamy tu do wyboru kilka technik (najpopularniejszych):
- trail division, czyli dzielimy daną liczbą przez wszystkie liczby pierwsze od 2 do pierwiastka z tej liczby. Obliczenia wymagają małej ilości pamięci ale olbrzymiej ilości czasu.
- P-1, metoda opracowana przez Johna Pollarda, która bazuje na małym twierdzeniu Fermata, i opiera się na szukaniu GCD. Nie wymaga dużych ilości pamięci ale ze względu na czas obliczeń nadaje się głównie do poszukiwania relatywnie dużych dzielników, tam gdzie metoda trial division staje już zasadniczo nie użyteczna bo dzielenie trwało zbyt długo.
- ECM, czyli metoda krzywych eliptycznych (Lenstra), która w zasadzie też poszukuje GCD ale różni się metodą wyboru kandydatów.
Żadna z tych metod przy obecnym stanie techniki nie nadaje się do 100% potwierdzenia pierwszości liczby. Ponieważ metody te mogą potrzebować wielu lat na weryfikację czy bardzo duża liczba jest pierwsza. Mimo to są użyteczne w pewnym ograniczonym zakresie do odnajdywania relatywnie małych dzielników dla dużych kandydatów na liczbę pierwszą.
2). Metody sitowe, polegające na odsianiu z pewnego zbioru liczb które są lub nie są pierwsze. I tu w zasadzie mamy dwie najpopularniejsze techniki:
- sito Arastotenesa, znane chyba wszystkim ze szkoły średniej, polegająca na odrzucaniu ze zbioru liczb które są kolejnymi wielokrotnościami liczb pierwszych. Obliczenia są szybkie ale wymagają dużej ilości pamięci.
- sito Atkina, które działa na podobnej zasadzie ale wykorzystuje arytmetykę modulo. Jest szybsze niż sito Erastotenesa i wymaga mniej pamięci.
Jednakże te metody sitowe nie nadają się dla dużych liczb ponieważ wymagały by olbrzymich ilości pamięci (pojedyncze liczby zajmują megabajty a trzeba by ich przetrzymywać ogromne ilości).

Istnieją jeszcze inne metody ale nie są to metody uniwersalne. Działają dla kandydatów na liczby pierwsze pewnego typu jak np. liczby Mersenne-a, Riesela, itp.

Są też metody probabilistyczne jak np. test Millera-Rabina. Ale są z nimi dwa zasadnicze problemy:
- W zasadzie ich wyniki nie wskazują czy dana liczba jest pierwsza a bardziej czy jest złożona. Tzn. jeśli test zwraca fałsz to znaczy że liczba na pewno jest złożona, natomiast jeśli zwraca prawdę to liczba jest prawdopodobnie pierwsza.
- Testy probabilistyczne do wyboru pewnych argumentów używają wartości losowych przy czym liczby te muszą posiadać pewne określone cechy. W związku z tym z pewnym prawdopodobieństwem może się zdarzyć tak że nie uda się wylosować żadnej liczby która te warunki spełnia i program w padnie w nieskończoną pętlę (przed czym oczywiście można się zabezpieczyć ustawiając odpowiedni limit prób). Tyle że z punktu widzenia użyteczności w zasadzie wystarczy że program "będzie miał pecha" i będzie potrzebował bardzo długiego czasu na wylosowanie odpowiednich liczb żeby okazał się nieefektywny.

P.S. Np. w Mersenne@home w pre-kalkulacji wykorzystuję sito Atkina do znajdywania wszystkich liczb pierwszych do poziomu (2^64)-1, i używam ich jako dzielników do trial division. Oczywiście żeby sprawę przyśpieszyć używam także innych ułatwień wynikających z małego twierdzenia Fermata, za pomocą których udaje się jeszcze zmniejszyć liczbę dzieleń o jeden czy dwa rzędy wielkości. I dzięki temu szybko odsiewam 15-20% kandydatów.

[goofyx]

A wracając do stawiania serwera projektu boinc.
Czy ktoś ma może namiar na taką instrukcje krok po kroku dla laika w linuksie.

[GRID]

Krzyszp mówił że na potrzeby Polskiego projektu BOINC PPB nawet przetłumaczyli wszystkie materiały. Ale to było jakiś czas temu i te materiały mogą być nie aktualne. Tak czy siak to chyba wcześniej trzeba trochę Debiana poćwiczyć.

[emik]

A wracając do stawiania serwera projektu boinc.
Czy ktoś ma może namiar na taką instrukcje krok po kroku dla laika w linuksie.

instrukcja kolegów z PNT:

Kod [Zaznacz] Rozwiń

http://boinc.pl/forum/viewtopic.php?f=115&t=174

[goofyx]

A wracając do stawiania serwera projektu boinc.
Czy ktoś ma może namiar na taką instrukcje krok po kroku dla laika w linuksie.

instrukcja kolegów z PNT:

Kod [Zaznacz] Rozwiń

http://boinc.pl/forum/viewtopic.php?f=115&t=174

Dobre!
Tego nie widziałem <- sprawdzę na wirtualce :)

[goofyx]

Zrobiłem wszystko według instrukcji z forum PNT co do joty, ale jak daje MAKE to wywala mi taki błąd:




Jakieś pomysły?

[Troll81]

prawa do plików?

[buninek]

../libtool: line 990: g++: nie znaleziono polecenia

Nie zainstalowałeś kompilatora C++.

Możesz zmienić język komunikatów na angielski. Google, będzie wtedy bardziej pomocne.

Kod [Zaznacz] Rozwiń

LC_ALL=C make

[goofyx]

../libtool: line 990: g++: nie znaleziono polecenia

Nie zainstalowałeś kompilatora C++.

Możesz zmienić język komunikatów na angielski. Google, będzie wtedy bardziej pomocne.

Kod [Zaznacz] Rozwiń

LC_ALL=C make

Popatrzę wieczorem <- dzięki.

[buninek]

Mały update.
Zajrzyj tu http://boinc.berkeley.edu/trac/wiki/ServerIntro. Przejdź do akapitu "Common problems".

Standardowym kompilatorem C++ w systemach GNU/Linux jest g++. W systemie możesz mieć jednocześnie zainstalowanych kilka jego wersji, od g++-3.3.6 po g++-4.6.

Czyli, mogłeś zainstalować "jakaś" wersję :) a nie masz linku do /usr/bin/g++. Sprawdź.

Kod [Zaznacz] Rozwiń

ls /usr/bin/g++-*
Jeśli jest, to zrób link symboliczny z odpowiedniej wersji do /usr/bin/g++. Jak nie ma, zainstaluj paczkę.

Zamiast symlinku można wyeksportować odpowiednią zmienną (CXX - kompilator C++), przykładowo.

Kod [Zaznacz] Rozwiń

export CXX=/usr/bin/g++-4.5.6
Z tym, że musi być to zrobione przed autoconf lub configure.

[goofyx]

hmm, dzięki za podpowiedzi <- dzięki nim doszedłem do tego że nie miałem kompilatora g++ zainstalowanego.

Teraz mam nowy problem <- ale to na jutro ;)
Utworzyłem projekt, nadałem prawa zgodnie z instrukcją <- ale jak robie: adres_serwera/tah <- to mi pokazuje, że nie może znaleźć ;)