Matematyka.pl

Jaka jest szybsza metoda od sita erastotenesa by znaleźć liczby pierwsze.

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

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.

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

Pozdrawiam, GNicz

Heh mój też taki raczej nie za bardzo, ale wystarczyło by dostać 6 z informy.

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

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

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)

Najdluzsza znaleziona liczba pierwsza ma 1 000 000 cyfr.

long double? Przeciez to typ zmiennoprzecinkowy.

Pozdrawiam, GNicz

No to co, że zmienno przecinkowy ale najdłuższy!

hehehe to sie pewnego dnia przeliczysz:)

ps zapoznaj sie z wlasciwosciami zmiennoprzcinkowego zapisu liczb

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

Pozdrawiam, GNicz

Wiecie co może macie racje użyje typu __int64

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

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