Pytania otagowane jako primes

5
Kompresja danych przy użyciu liczb pierwszych
Niedawno natknąłem się na następujący interesujący artykuł, który twierdzi, że skutecznie kompresuje losowe zestawy danych o zawsze ponad 50%, niezależnie od rodzaju i formatu danych. Zasadniczo używa liczb pierwszych do unikalnego skonstruowania reprezentacji 4-bajtowych fragmentów danych, które są łatwe do zdekompresowania, biorąc pod uwagę, że każda liczba jest unikalnym produktem …
1
Czy ustalenie, czy istnieje liczba pierwsza w przedziale, o którym wiadomo, że jest w P czy NP-zupełna?
Widziałem z tego postu przy przepełnieniu stosu, że istnieją pewne stosunkowo szybkie algorytmy przesiewania przedziału liczb, aby sprawdzić, czy jest liczba pierwsza w tym przedziale. Czy to jednak oznacza, że ​​ogólny problem decyzyjny: (Czy istnieje liczba pierwsza w przedziale?) Znajduje się w P. (Było wiele odpowiedzi na ten post, których …
3
Teoretyczna złożoność trudna do sprawdzenia wartości
Funkcja zliczania liczb pierwszych , zdegradowana , jest zdefiniowana jako liczba liczb pierwszych mniejsza lub równa x .π(x)π(x)\pi(x)xxx Możemy zdefiniować problem decyzyjny z w następujący sposób:π(x)π(x)\pi(x) Biorąc pod uwagę dwie liczby i n , zapisane binarnie, zdecyduj, czy π ( x ) = n .xxxnnnπ(x)=nπ(x)=n\pi(x) = n Rozmawiałem dziś z …
3
Dlaczego Miller – Rabin zamiast testu pierwotności Fermata?
Z dowodu Millera-Rabina , jeśli liczba przechodzi test pierwotności Fermata , musi również przejść test Millera-Rabina z tą samą podstawą (zmienną w dowodzie). A złożoność obliczeń jest taka sama.zaaa Z testu pierwotności Fermata wynika : Chociaż liczby Carmichaela są znacznie rzadsze niż liczby pierwsze, 1 jest ich wystarczająco dużo, aby …
2
Wydajne obliczanie najmniejszej liczby całkowitej za pomocą n dzielników
Aby rozwiązać ten problem, po raz pierwszy to zauważyłem ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Gdzie to liczba (niekoniecznie pierwsza) dzielników . Jeśli jest najmniejszą liczbą całkowitą taką, że , toϕ(m)ϕ(m)\phi(m)mmmmmmϕ(m)=nϕ(m)=n\phi(m) = n ϕ(m)=nϕ(m)=n\phi(m) = n (e1+1)(e2+1)⋯(ek+1)=n(e1+1)(e2+1)⋯(ek+1)=n(e_1 + 1)(e_2 …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.