Jak policzyć ile jest 200-cyfrowych liczb pierwszych?

1

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ę.

1

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).

1

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.

0

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 :)

2

Hint: profesor Cię trolluje.

6

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

0

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

0

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 ;)

1

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ą?

0

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)

0
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ą.

3
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×10197 a 1.970×10197

0

@datdata zawsze można profesora strollować :p

0

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.

1

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
1

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.

2

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 :]

1 użytkowników online, w tym zalogowanych: 0, gości: 1