Jak policzyć ile jest 200-cyfrowych liczb pierwszych?

Witam,

Mam do Was takie pytanko, czy jestem w stanie sam policzyć ile jest 200-cyfrowych liczb pierwszych? Potrzebuję programiku (obojętnie w jakim języku), który mi to obliczy na w "miarę" normalnym sprzęcie w "miarę" dobrym czasie.

Da radę to wykonać, można to traktować jako zlecenie i zaproponować swoje rozwiązanie(pomoc) na pw. Powiedzmy, że chodzi o dość interesującą sprawę ;)

Pozdrawiam i z góry dziękuję.

IMO jedynie co możesz zrobić by uzyskać wynik przybliżony to skorzystać z aproksymacji funkcji Pi.
Wynik dokładny będzie bardzo duży (w long in się nie zmieści na pewno) i nie sądzę by dało się to liczyć w rozsądnym czasie (inaczej cała współczesna kryptografia by się posypała).

Nie ma szans. Samo przeiterowanie przez wszystkie liczby dwustocyfrowe trwałoby (zakładając, że jedną liczbę analizowalibyśmy nanosekundę) trwałoby circa 10^187 lat.

Bo jest taka sytuacja:
Profesor da zaliczenie i 5 do indeksu jeśli mu w jakiś sposób pokażę ile jest takich liczb, dokładnie ( nie oszacować ). Oferta bardzo kusząca, a jak to student, skusiłem się na taką propozycje i chcę coś pokombinować, szukam algorytmu, który zoptymalizuje jakoś ten czas, może skombinowałbym dostęp do jakiegoś komputera do zadań specjalnych :)

Hint: profesor Cię trolluje.

No to walnij aproksymację, a pozostałe cyfry uzupełnij losowo i niech ci udowodni, że jest źle :P.

Strzel dowolną liczbę - profesor tak samo jak i Ty nie będzie w stanie tego sprawdzić

Wiecie, jakoś mu muszę wytłumaczyć, powiedzieć jak to zrobiłem, przecież nie powiem, że uzupełniłem losowo, no tak to nie za działa ;)

Niemożliwe na Twoją głowę ani nikogo tutaj na forum
Tak samo dla Twojego profesora - odpuść sobie bo nie dostaniesz tej 5-tki

Ale swoją drogą ciekawe jest - największa odkryta liczba pierwsza ma 17 425 170 cyfr. W jaki sposób sprawdzili jej pierwszość?
Tak samo jest nagroda "150 tysięcy dolarów dla odkrywcy liczby pierwszej o więcej niż 100 milionach cyfr" - w jaki sposób to sprawdzą?

Dla pewności, że nadzieja na nie pisanie egzaminu przepadła się Was spytam, czy może wiecie, czy któraś z instytucji mogłaby obliczyć nie jakie są te liczby, tylko po prostu ile jest takich 200 cyfrowych liczb pierwszych? (jeśli mam tam kogoś znajomego)

7tomas7 napisał(a):

Dla pewności, że nadzieja na nie pisanie egzaminu przepadła się Was spytam, czy może wiecie, czy któraś z instytucji mogłaby obliczyć nie jakie są te liczby, tylko po prostu ile jest takich 200 cyfrowych liczb pierwszych? (jeśli mam tam kogoś znajomego)

Spróbuj w NSA, jak ktoś ma aż tak dobre komputery to tylko oni. Ew KGB (dzisiaj FSB), być może znają jakieś "skróty". Co prawda Google i NASA mają superkomputery kwantowe, ale akurat do tego raczej się póki co nie nadają.

7tomas7 napisał(a):

Wiecie, jakoś mu muszę wytłumaczyć, powiedzieć jak to zrobiłem, przecież nie powiem, że uzupełniłem losowo, no tak to nie za działa ;)
ale zapewne to jest test na zaradność. Dokładnie na pewno tego nie policzysz w rozsądnym czasie.
A wzory na aproksymację funkcji Π dostałeś od mnie w linku.

Mi wychodzi, że ta liczba mieści się pomiędzy:
1.945×10¹⁹⁷ a 1.970×10¹⁹⁷

@datdata zawsze można profesora strollować :p

U mnie na studiach tez jeden doktor obiecał że jak ktoś pokaże na plaszczyznie 2D, 3 wektory liniowo niezalezne to dostanie 5 na koniec na zaliczenie:) A najlepsze ze sie chetny znalazl, jeszcze gosciu naprowadzal go pytaniami, a moze Pan zle wektory wybrał, a może by tak spróbować... 5 na koniec nie było, za to była 2 na miejscu.

Da się:

• poczekaj aż na rynku pojawi się kilka trylionów komputerów kwantowych,
• napisz niewykrywalnego wirusa który zainfekuje je programem liczącym liczby pierwsze w przedziale
• licz rownolegle
• jest szansa ze skonczysz w najblizsze kilkaset lat

EDIT:

• jest jeszcze druga opcja. Zmyślasz dowolną liczbę z oszacowanego przedziału
• znajdujesz nazwisko dowolnego chińskiego naukowaca który zajmuje się liczbami pierwzymi i ma publikacje tylko po chinsku
• dajesz profesorowi ta liczbe i mowisz ze na podstawie badan naukowych tego i tego goscia i ze nie rozumiesz jak on to policzyl do konca
• prosisz go zeby udowpdnil ze to nie jest wynik jesli watpi - jesli sie podejmie to bedzie martwy znim skonczy

35932340132911728215919248929173324689470603647745153279587214828873784509384805239440875075822787013388864959540134123346192235120510701414630932745355140703703015525102519512818642714308752327257691 proszę bardzo. Obliczone przy pomocy wolfram alpha w niecałe 10 sek. Jeśli nie wierzysz to daje query i sam sprawdź: 200 digits prime numbers. Cała przyjemność po mojej stronie.

PS jeśli masz napisać program to zrób aplikacje która pobiera ta liczbę ze strony.

Hipoteza Riemanna - Zagadka Wszechczasów - od 28:00

Teraz proszę wyjaśnijcie mi, jeżeli wyznaczenie dwustucyfrowych liczb pierwszych współcześnie trwało by tak niesamowicie długo, to w jaki sposób ta firma weszła w posiadanie liczb pierwszych, złożonych ze 150 milionów cyfr? Ja nie znam odpowiedzi i nie ukrywam, że chciałbym ją poznać;

Czy może te słowa lektora:

[...] W tych sejfach trzymamy liczby pierwsze, na których opiera się bezpieczeństwo wymiany informacji w sieci, a co za tym idzie - transakcji internetowych. Tym produktem są liczby pierwsze, złożone z ponad 150 milionów cyfr. Z tak wielkimi liczbami nie potrafią uporać się nawet superkomputery. [...]

należy interpretować inaczej? Matematykiem nie jestem - po prostu jestem ciekawy :]