Algorytm wyszukiwania liczb pierwszych

Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

Jaka jest szybsza metoda od sita erastotenesa by znaleźć liczby pierwsze.
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

Algorytm wyszukiwania liczb pierwszych

Post autor: gnicz »

Rozne testy podzielnosci, albo szukanie dzielnikow pierwszych. Gdzies mam o tym artykul (mojego autorstwa) lecz nie dokonczony. Jesli jestes zainteresowany to dam znac gdy skoncze. Zrobilem sobie liste liczb pierwszych az do 2847729019 (przy pomocy wlasnych programow).

Pozdrawiam, GNicz
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

Właśnie potrzeba mi tego do progsa, bo napisałem taki jeden ale używa sita erastotenesa i do miliona dochodzi w jakieś 12 sek.
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

Algorytm wyszukiwania liczb pierwszych

Post autor: gnicz »

Moj program jest bardzo niekompletny, powiedzialbym ze pisany na kolanie. Jak dobrze pojdzie to do niedzieli skoncze.

Pozdrawiam, GNicz
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

Heh mój też taki raczej nie za bardzo, ale wystarczyło by dostać 6 z informy.
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

Algorytm wyszukiwania liczb pierwszych

Post autor: gnicz »

A na jakich liczbach operujesz?

Ja mam dzialajacy algorytm w C, na liczbach 32-bit i niekomplenty w assemlberze dla liczb dowolnej wielkosci (oczywiscie ogranioczne jest to iloscia pamieci).

Na marginesie: sa przydzielane pieniezne nagrody za znalezienie najwiekszej liczby pierwszej.

Pozdrawiam, GNicz
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

Algorytm wyszukiwania liczb pierwszych

Post autor: arigo »

tez taki progs w C napisalem swojego czasu
wlasnie 32 bity to pewna granica dla i386 ale moje wstawki w asm to rozwiazaly i dzieki temu dodanie 2 liczb 64 bit zajmowalo tyle co dodanie 4 liczb 32 bit co bylo barzdo optymalne poniewaz taka implementacja w C jest duzo wolniejsza
ale to nie zmienia faktu ze i tak przy duzych liczbach troche takie szukanie trwalo
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

O nagrodach wiem ale największa liczba pierwsza ma chyba 200 zer albo i więcej.

Pozatym piszę w C++ na Borland C++ Builder.

Używam typu long doube (80bit)
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

Algorytm wyszukiwania liczb pierwszych

Post autor: gnicz »

Najdluzsza znaleziona liczba pierwsza ma 1 000 000 cyfr.

long double? Przeciez to typ zmiennoprzecinkowy.

Pozdrawiam, GNicz
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

No to co, że zmienno przecinkowy ale najdłuższy!
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

Algorytm wyszukiwania liczb pierwszych

Post autor: arigo »

hehehe to sie pewnego dnia przeliczysz:)

ps zapoznaj sie z wlasciwosciami zmiennoprzcinkowego zapisu liczb
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

Algorytm wyszukiwania liczb pierwszych

Post autor: gnicz »

Tyle ze w zmiennoprzecinkowych czesc bitow jest przeznaczona na ceche, czesc na mantyse oraz jeden bit na znak.

Pozdrawiam, GNicz
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

Wiecie co może macie racje użyje typu __int64
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

Algorytm wyszukiwania liczb pierwszych

Post autor: arigo »

na long double nie dosc ze by bylo nieoptymalnie ze wzgledu na czas to jeszcze dlugosc by nie byla taka duza bo Ciebie interesuje dokladnosc do jednosci
Hetacz
Użytkownik
Użytkownik
Posty: 292
Rejestracja: 13 paź 2004, o 13:15
Płeć: Mężczyzna
Lokalizacja: Komorow k/Warszawy

Algorytm wyszukiwania liczb pierwszych

Post autor: Hetacz »

Nie pomyślałem o tym, choć jak narazie program sprawuje się dobrze.
ODPOWIEDZ