Check Prime Number

Q: Jaka jest złożoność czasowa sprawdzania, czy liczba jest pierwsza?

Dzielenie próbne do √n zajmuje O(√n) czasu i O(1) pamięci. Dla n do 2^31-1 oznacza to najwyżej około 46,000 dzieleń lub 23,000 , jeśli pomijasz parzyste dzielniki. Sprawdzanie każdego dzielnika do n-1 ma złożoność O(n) i wymaga około dwóch miliardów kroków dla największego wejścia.

Q: Dlaczego sprawdzasz tylko dzielniki do pierwiastka kwadratowego z n?

Dzielniki występują w parach d i n / d , których iloczyn wynosi n . Gdyby oba były większe niż √n , ich iloczyn byłby większy niż n . Zatem w każdej parze jeden z elementów jest nie większy niż √n , a jeśli do tego momentu nie znajdziemy żadnego dzielnika, n jest liczbą pierwszą.

Q: Czy 1 jest liczbą pierwszą?

Nie. Liczba pierwsza ma dokładnie dwa różne dzielniki: 1 i samą siebie, a 1 ma tylko jeden. Pominięcie 1 sprawia, że rozkład każdej liczby całkowitej dodatniej na czynniki pierwsze jest jednoznaczny. Dlatego isPrime(1) zwraca false .

Q: Czy istnieje szybszy sposób na sprawdzanie, czy bardzo duże liczby są pierwsze?

Dla jednej 32-bitowej liczby dzielenie próbne do √n jest wystarczająco szybkie. W przypadku liczb mających dziesiątki cyfr programy używają testu Millera-Rabina, który sprawdza kilka potęg modulo zamiast próbować kolejnych dzielników. Aby wypisać wszystkie liczby pierwsze nie większe niż dany limit, sito Eratostenesa sprawdza się lepiej niż testowanie każdej liczby osobno.

PoczątkującyMatematyka i symulacja

+10

Liczba pierwsza to liczba całkowita większa niż 1, której jedynymi dzielnikami są 1 i ona sama. Otrzymujesz dodatnią liczbę całkowitą n. Zwróć true, jeśli n jest liczbą pierwszą, a w przeciwnym razie false. Liczba 1 nie jest liczbą pierwszą.

Funkcja

isPrime(n: integer) → boolean

ninteger: dodatnia liczba całkowita do sprawdzenia
Zwracaboolean: true, jeśli n jest liczbą pierwszą, w przeciwnym razie false

Ograniczenia

1 ≤ n ≤ 2³¹ - 1

Przykłady

Wejście: n = 29
Wyjście: true
Wyjaśnienie: Żadna z liczb 2, 3, 4 ani 5 nie dzieli 29, a 6 × 6 = 36 przekracza już 29, więc nie ma już dzielników do znalezienia. 29 jest liczbą pierwszą.

Wejście: n = 1
Wyjście: false
Wyjaśnienie: Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. 1 ma tylko jeden dzielnik, więc odpowiedź to false.

Wejście: n = 91
Wyjście: false
Wyjaśnienie: 91 wygląda na liczbę pierwszą, ale 7 × 13 = 91. Dzielnik 7 pojawia się, zanim wyszukiwanie przekroczy √91 ≈ 9.5.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Każda liczba pierwsza większa od 3 ma postać 6k-1 lub 6k+1. Czy możesz wykorzystać to, aby testować tylko jedną trzecią potencjalnych dzielników?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Definicja mówi, że należy wykluczyć wszystkie dzielniki od 2 do n-1, co dla największej liczby pierwszej będącej argumentem wejściowym oznacza ponad dwa miliardy dzieleń. Dzielniki występują w parach, których iloczyn wynosi n, a mniejszy z każdej pary jest nie większy niż √n. Dlatego szukasz tylko do √n, co najwyżej około 23,000 nieparzystych kandydatów.

Wypróbuj każdy dzielnik

Poprawne, ale nie kończy się na największych testach

Intuicja

Definicja podaje algorytm. Liczba n ≥ 2 jest pierwsza, gdy żadna z liczb 2, 3, ..., n-1 jej nie dzieli. Sprawdź każdy kandydat d za pomocą n % d == 0 i zwróć false przy pierwszym dzielniku. Dla 91 pętla sprawdza liczby od 2 do 6 i zatrzymuje się przy 7.

Najpierw obsłuż przypadek n < 2. Dla n = 1 zakres kandydatów jest pusty, więc pętla nigdy nie znajdzie dzielnika i uzna 1 za liczbę pierwszą.

Liczby złożone zwykle powodują szybkie zakończenie, ale liczba pierwsza przechodzi każdy test, więc pętla wykonuje się do końca. Dla n = 2147483647, która jest liczbą pierwszą, oznacza to około 2.1 × 10^9 dzieleń — znacznie więcej, niż można wykonać w kilka sekund.

Algorytm

Jeśli n < 2, zwróć false.
Przechodź pętlą przez wartości d od 2 do n-1.
Jeśli n % d == 0, zwróć false.
Po pętli zwróć true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Próba dzielenia do pierwiastka kwadratowego

Intuicja

Dzielniki występują w parach. Jeśli d dzieli n, to n / d również dzieli n, a ich iloczyn wynosi n. Nie mogą być oba większe niż √n, bo wtedy ich iloczyn byłby większy niż n. Zatem jeśli n ma jakikolwiek dzielnik poza 1 i samym sobą, to ma dzielnik nie większy niż √n. Dla 91 para to 7 i 13, a 7 ≤ 9.5. Jeśli żaden dzielnik nie większy niż √n nie dzieli n, to żaden większy od niego również tego nie robi.

Zapisz ograniczenie jako d * d ≤ n, zamiast wywoływać funkcję pierwiastka kwadratowego. Dzięki temu pozostajesz w liczbach całkowitych, bez zaokrągleń. Znak równości ma znaczenie: 49 = 7 × 7, a jego jedyny dzielnik 7 znajduje się dokładnie w punkcie √49.

Możesz też pominąć połowę kandydatów. Rozpatrz osobno 2: parzyste n jest liczbą pierwszą tylko wtedy, gdy wynosi 2. Po tym sprawdzeniu nieparzyste n ma tylko nieparzyste dzielniki, więc zacznij od 3 i zwiększaj wartość o 2. Dla n = 2147483647 pętla wykonuje teraz około 23,000 iteracji zamiast 2.1 × 10^9.

Algorytm

Jeśli n < 2, zwróć false.
Jeśli n jest parzyste, zwróć informację, czy n == 2.
Ustaw d na 3 i wykonuj pętlę, dopóki d * d ≤ n, używając typu 64-bitowego dla d.
Jeśli n % d == 0, zwróć false. W przeciwnym razie dodaj 2 do d.
Po zakończeniu pętli zwróć true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Pułapki i przypadki brzegowe

Całą ideę można wyrazić w jednym wierszu. Błędy pojawiają się na granicach: dla najmniejszych danych wejściowych i ostatniego dzielnika.

Zwracanie true dla 1. Ma jeden dzielnik, a nie dwa, więc nie jest liczbą pierwszą.
Odrzucanie 2, ponieważ jest parzyste. Sprawdź n == 2, zanim odrzucisz liczby parzyste.
Wykonywanie pętli, gdy d * d < n, zamiast ≤. Wtedy kwadraty liczb pierwszych, takich jak 9, 49 i 2147117569 = 46337², są uznawane za liczby pierwsze.
Przepełnienie w d * d. W 32-bitowym typie int wartość 46341 × 46341 = 2147488281 się nie mieści i zawija się do liczby ujemnej, więc warunek nadal jest spełniony, a pętla wykonuje się znacznie dalej niż do √n. Użyj 64-bitowego typu dla d albo porównuj d ≤ n / d.
Wyznaczanie granicy za pomocą zmiennoprzecinkowego sqrt i obcinanie wyniku. double jest dokładny dla każdej wartości n w tym przypadku, ale dla wejściowych wartości 64-bitowych zaokrąglenie może dać wynik o jeden mniejszy od prawdziwego pierwiastka i pominąć jedyny istotny dzielnik. d * d ≤ n nie niesie takiego ryzyka.

Najczęstsze pytania4

Jaka jest złożoność czasowa sprawdzania, czy liczba jest pierwsza?

Dzielenie próbne do √n zajmuje O(√n) czasu i O(1) pamięci. Dla n do 2^31-1 oznacza to najwyżej około 46,000 dzieleń lub 23,000, jeśli pomijasz parzyste dzielniki. Sprawdzanie każdego dzielnika do n-1 ma złożoność O(n) i wymaga około dwóch miliardów kroków dla największego wejścia.

Dlaczego sprawdzasz tylko dzielniki do pierwiastka kwadratowego z n?

Dzielniki występują w parach d i n / d, których iloczyn wynosi n. Gdyby oba były większe niż √n, ich iloczyn byłby większy niż n. Zatem w każdej parze jeden z elementów jest nie większy niż √n, a jeśli do tego momentu nie znajdziemy żadnego dzielnika, n jest liczbą pierwszą.

Czy 1 jest liczbą pierwszą?

Nie. Liczba pierwsza ma dokładnie dwa różne dzielniki: 1 i samą siebie, a 1 ma tylko jeden. Pominięcie 1 sprawia, że rozkład każdej liczby całkowitej dodatniej na czynniki pierwsze jest jednoznaczny. Dlatego isPrime(1) zwraca false.

Czy istnieje szybszy sposób na sprawdzanie, czy bardzo duże liczby są pierwsze?

Dla jednej 32-bitowej liczby dzielenie próbne do √n jest wystarczająco szybkie. W przypadku liczb mających dziesiątki cyfr programy używają testu Millera-Rabina, który sprawdza kilka potęg modulo zamiast próbować kolejnych dzielników. Aby wypisać wszystkie liczby pierwsze nie większe niż dany limit, sito Eratostenesa sprawdza się lepiej niż testowanie każdej liczby osobno.