Ilość dwustu cyfrowych liczb pierwszych - program.

[ZajcuNS]

Witam,
Postaram się owe zagadnienie przedstawić... znaczy może nie tyle zagadnienie, co polecenie.

Sprawa wygląda tak:
Mój wykładowca od matematyki dyskretnej zarzucił temat, że: "dam zaliczenie osobie, która przedstawi mi program, może być w c++ lub dowolny język, który wykaże ilość dokładnie liczb pierwszych dwustu cyfrowych. Przyznam się, że sam tego nie wiem. Jeśli wytłumaczenie będzie przekonywujące dam zaliczenie beż żadnego zawahania"

Więc jak to student, który chce mieć coś, za w sumie zrobienie niewiele zacząłem się nad tym zastanawiać.
Nie ukrywam, że matematyk zemnie żaden więc Proszę Was o pomoc.

Nad czym ja się zastanawiam.
Gdzie jest haczyk? Przecież definicja liczby pierwszej jest jasna i klarowna więc sprawdzanie takowych liczb z przedziału do 200cyfrowej liczny nie wydaje się trudne co bardziej czasochłonne również dla komputera. Znajomy który dość dobrze programuje mówi, przyznając się, że nie zna problemu tak dobrze mówi, że PC'ty mają dość duże zagwostki z liczbami pierwszymi, że niekoniecznie sobie z nimi radzą.

Więc teraz w sumie proszę Was o jakąś dyskusję na owy temat, która może poprowadzi mnie do rozwiązania lub wyjaśni, że nie ma to sensu.
Pozdrawiam i z góry dziękuję.
Kamil.

[jarzabek89]

Nie ma szans tego zrobić na zwykłym komputerze, nie masz się nawet co za to zabierać.

[ZajcuNS]

Hm... ale może jakbym przyniósł sam kod z sensownym wytłumaczeniem to a nóż by zaliczył.
A jak będzie miał możliwość to sam sobie skoczy z UJ na AGH gdzie mają to nowe monstrum i sobie policzy

[jarzabek89]

Nawet nowe monstrum AGH nie jest w stanie tego zrobić.

EDIT: jest w stanie.Za kilka tysięcy lat jak dzisiaj odpalisz

[ZajcuNS]

No zapewne masz racje.
A domyślasz się takowej długości czasu sugerując się z której złożoności obliczeniowej danego algorytmu do liczb pierwszych?

[kalwi]

największa liczba jaką może przechować zmienna w języku C/C++ jest typu unsigned long long int i wynosi \(\displaystyle{ 18 446 744 073 709 551 615}\) - więc tu raczej tego nie zrobisz (co oczywiście nie jest niemożliwe). Masz przeszukać przedział

\(\displaystyle{ 1\underbrace{000 \ \dots \ 000}_{\imbox{199 \ zer}} \ - \ \underbrace{999 \ \dots \ 999}_{\imbox{200 \ dziewiatek}}}\)

A sitem Erystotenesa przeszukanie przedziału \(\displaystyle{ 0-1000000}\) na moim komputerze (którego bym określił jako średni pod względem mocy obliczeniowej) zajęło 11 sekund prawie. A to jest tylko 7 cyfr. A "na siłę" szybiciej się nie da (przynajmniej znanymi mi sposobami), bo złożoność sita wynosi \(\displaystyle{ O\left( n\log_2\log_2 n\right)}\). Krótko mówiąc prowadzący sobie z was zrobił jaja.

[ZajcuNS]

Cóż, szkoda.
Kalwi, dziękuję za Twoją odpowiedź.

[gryxon]

To że maksymalna zmienna w c++ jest taka a nie inna to nie jest żaden argument. Być może istnieje jakaś zależność matematyczno/algorytmiczna, która potrafi oszacować liczbę tych liczb dwustucyfrowych. Aczkolwiek też mi się wydaje, że egzaminator jest złośliwy ;p

[ZajcuNS]

Znaczy też chyba trzeba wziąć pod uwagę to że im liczba pierwsze jest większy tym następna jest dalej niż jej poprzednik. Ta liczba k-liczb miedzy nimi się zwiększa. Czy jakoś tak to było.

[kalwi]

To że maksymalna zmienna w c++ jest taka a nie inna to nie jest żaden argument. Być może istnieje jakaś zależność matematyczno/algorytmiczna, która potrafi oszacować liczbę tych liczb dwustucyfrowych. Aczkolwiek też mi się wydaje, że egzaminator jest złośliwy ;p

Ja nie powiedziałem, że się nie da w C++ tego oszacować - tylko napisałem, że metodą siłową, jaką zaproponował autor w pierwszym poście nie pójdzie tego zrobić (chociaż python z tego co pamiętam nie ma chyba takich ograniczeń)

[gryxon]

Może jakieś szacowania spróbować zrobić? Chociaż, pewnie szkoda czasu ;p

[jarzabek89]

Moich kalkulacji szacunkowych wynika,że największa liczba 200 cyfrowa zmieści się jakoś na 667 bitach. Znając wynik x*y, gdzie x i y sa liczbami pierwszymi, znalezienie liczb x,y dla 750bitowego wyniku zajęło 2 lata(nie wiem na jakim sprzęcie,ale domyślam się,że nie na zwykłym laptopie). Dla jednej pojedynczej liczby zaznaczam. Zwiększenie o jeden bit,kilka bitów prowadzi do tego że obliczenia trwałyby kilkadziesiąt/tysiące lat.
Tutaj mamy nieco inny problem, ale tylko obrazuje, z jak wielkimi wartościami mamy tutaj do czynienia.
Szacowanie ile jest liczba pierwszych w danym zakresie nie jest równe dokładnej ilości.
Poza tym skoro nie wiemy po dzień dzisiejszy jak zachowują się liczby pierwsze, to nie da się szacować ile ich jest.

[ZajcuNS]

Jeszcze raz dziękuje Wam za odpowiedzi jak i udział w dyskusji.
Pozostaje mi tylko wyjaśnić to wykładowcy i zapytać czy kpił czy mówił serio

[a4karo]

Matematyka zna doś dobry wzór na ilośc liczb pierwszych nie większych od \(\displaystyle{ n}\). poszukaj go w necie i zastosuj.

Jak nie uwierzy w odpowiedź, to niech napisze program i policzy

[Afish]

Sprawdzenie dwustucyfrowej liczby nie jest trudne, obecnie da się to zrobić w ułamku sekundy wykorzystując test Millera-Rabina i jemu podobne (

Kod: Zaznacz cały

http://probableprime.org/images/primality-times.png

). Wprawdzie jest on probabilistyczny, ale prawdopodobieństwo pomyłki jest zbyt małe, aby się tym przejmować. Są projekty poszukujące dużych liczb pierwszych, ludzkość zna już takie liczby mające miliony cyfr:

Kod: Zaznacz cały

http://www.primegrid.com/

Problemem jest ogromna liczba kandydatów. Ustalenie liczby liczb pierwszych z danego przedziału to obliczanie funkcji \(\displaystyle{ \pi}\), póki co znane są jej wartości dla liczb rzędu \(\displaystyle{ 10^{25}}\), więc jeszcze sporo brakuje.

Moich kalkulacji szacunkowych wynika,że największa liczba 200 cyfrowa zmieści się jakoś na 667 bitach.

663 dokładniej.

Znając wynik x*y, gdzie x i y sa liczbami pierwszymi, znalezienie liczb x,y dla 750bitowego wyniku zajęło 2 lata(nie wiem na jakim sprzęcie,ale domyślam się,że nie na zwykłym laptopie).

To jest zupełnie inny problem, niż test pierwszości.