Ustal ilość liczb pierwszych dla danego n

[Chichot Hioba]

Dla danego \(\displaystyle{ n}\) trzeba znaleźć ilość liczb pierwszych, takich, że:
\(\displaystyle{ p_1p_2\cdots p_k \le n}\)

Gdzie \(\displaystyle{ p_1 = 2, p_2 = 3, p_3 = 5, \dots}\)

Nie ruszę...
Adoptuję każdy pomysł, będzie w dobrych rękach, obiecuję

[pesel]

Adoptuję każdy pomysł, będzie w dobrych rękach, obiecuję

Chyba "adaptuję"?

[Chichot Hioba]

pesel, nie. Żart, mimo że nie najwyższych lotów, to mimo wszystko napisany w miarę poprawnie.

[Premislav]

Skąd wziąłeś to zadanie? Raczej trudne to jest.

Nie widzę za bardzo możliwości sensownego policzenia tego, zostaje jakaś asymptotyka (twierdzenie o liczbach pierwszych na przykład) albo jakieś stosunkowo grube szacowania, chociażby \(\displaystyle{ p_k<e^{1+k}}\) czy \(\displaystyle{ p_k\le 2^{k+1}+1}\) (patrz jeden z moich ulubionych wątków: 131466.htm), przy czym w celu użycia do jakichś szacowań w zadaniu to drugie i tak trzeba osłabić, bo wygodnie mieć jakąś funkcję wykładniczą jako majorantę, a to z uwagi na ten iloczyn.
Ale może się mylę i istnieje sensowne rozwiązanie (chciałbym).

[Brombal]

Tak z grubsza
\(\displaystyle{ p_{i} \approx p_{i-1}+\ln(p_{i-1})}\)
\(\displaystyle{ \prod_{i=1}^{k} p_i \le n}\)
\(\displaystyle{ k}\) to ta szukana wartość

[Chichot Hioba]

Premislav, problem wyszedł sam podczas mojej zabawy liczbami. Jeszcze pomyślę.

Brombal, nie bardzo widzę co się tutaj stało poza powtórzeniem tezy. Mógłbyś rozwinąć?

[Kera]

Matematyk ze mnie marny, ale uważam że rozwiązaniem jest jakiś związek między sumą dzielników liczby \(\displaystyle{ N}\), a iloczynem \(\displaystyle{ N}\). Pewnie się mylę, ale chcesz adoptować jakiś pomysł, to proszę.

[Chichot Hioba]

związek między sumą dzielników liczby \(\displaystyle{ N}\), a iloczynem \(\displaystyle{ N}\)

Co to iloczyn liczby \(\displaystyle{ N}\)?

[Kera]

Miałem na myśli iloczyn wszystkich dzielników liczby \(\displaystyle{ N}\) ,a sumą tych dzielników.

[Chichot Hioba]

Kera, \(\displaystyle{ 16}\) ma dzielniki: \(\displaystyle{ 1,2,4,8,16}\)
\(\displaystyle{ 1+2+4+8+16 = 33}\)
\(\displaystyle{ 2\cdot 4 \cdot 8 \cdot 16 = 1024}\)

\(\displaystyle{ 17}\) ma dzielniki: \(\displaystyle{ 1, 17}\)
\(\displaystyle{ 1+17 = 18}\)
\(\displaystyle{ 1 \cdot 17 = 17}\)

Ciężko znaleźć powiązanie. Masz jakiś konkretniejszy pomysł? Co Ci nasunęło taką myśl?

[Kera]

Gdybyś znał sumę dzielników (zakładając że ktoś ci ją ujawnił) i ich iloczyn to już łatwo wyznaczyłbyś wszystkie dzielniki \(\displaystyle{ N}\), problem w tym że prawie nie ma sposobu wyznaczyć sumę na podstawie iloczynu. Jak rozwiążesz ten problem to rozwikłasz problem faktoryzacji. Zaznaczam jednak że marny ze mnie matematyk.

[Elayne]

Dla małych liczb można by skorzystać z ogólnie dostępnych w internecie baz danych liczb pierwszych zawierających kilkadziesiąt lub więcej milionów pierwszych liczb pierwszych lub skorzystanie z bardziej rozbudowanej bazy akademickiej.
W takim przypadku mamy dokładny wynik, np. 50-milionową liczbą pierwszą jest liczba \(\displaystyle{ 982 \ 451 \ 653}\).

[Brombal]

Dla małych liczb można by skorzystać z ogólnie dostępnych w internecie baz danych liczb pierwszych zawierających kilkadziesiąt lub więcej milionów pierwszych liczb pierwszych lub skorzystanie z bardziej rozbudowanej bazy akademickiej.
W takim przypadku mamy dokładny wynik, np. 50-milionową liczbą pierwszą jest liczba \(\displaystyle{ 982 \ 451 \ 653}\).

Tej wielkości liczby (np. 50-milionową) generuje się na zwykłym przeciętnym kompie w parę sekund. Przedwczoraj na zwykłym przeciętnym kompie wygenerowałem ok. 750 liczb pierwszych ponad 1000- cyfrowych, w czasie ok. 30 min. Problemem technicznym jest bardzo wielki przyrost p!.

[Elayne]

Podałem to jako przykład. Jeśli baza danych zawiera liczby pierwsze od 2 do liczb kilkudziesięciocyfrowych i interesuje nas ile jest liczb pierwszych mniejszych od powiedzmy \(\displaystyle{ 47 \ 055 \ 833 \ 462}\) to prostszym rozwiązaniem jest wysłanie zapytania do bazy; po chwili otrzymujemy wynik: 2-miliardową liczbą pierwszą jest liczba \(\displaystyle{ 47 \ 055 \ 833 \ 459}\).

[Brombal]

Następna liczba pierwsza po \(\displaystyle{ 47 \ 055 \ 833 \ 459}\) jest jedynie o \(\displaystyle{ 20}\) większą mógłbyś podrzucić link do tych akademickich baz?