Dlaczego sprawdzamy pierwiastek kwadratowy z liczby pierwszej, aby ustalić, czy jest ona liczbą pierwszą?

392

Aby sprawdzić, czy liczba jest liczbą pierwszą, czy nie, dlaczego musimy sprawdzać, czy można ją podzielić tylko do pierwiastka kwadratowego z tej liczby?

Patelnia
źródło
33
ponieważ jeśli n = a*bi a <= bwtedy a*a <= a*b = n.
Czy Ness
7
Aby to wyjaśnić, oznacza to, że musimy testować tylko do floor(sqrt(n)).
Acumenus

Odpowiedzi:

659

Jeśli liczba nnie jest liczbą pierwszą, można ją podzielić na dwa czynniki ai b:

n = a * b

Teraz ai bnie może być większa niż pierwiastek kwadratowy n, ponieważ wtedy produkt a * bbyłby większy niż sqrt(n) * sqrt(n) = n. Tak więc w każdej faktoryzacji nco najmniej jeden z czynników musi być mniejszy niż pierwiastek kwadratowy n, a jeśli nie możemy znaleźć czynników mniejszych lub równych pierwiastkowi kwadratowemu, nmusi być liczbą pierwszą.

Sven Marnach
źródło
Jak sqrt(n)musi być wystarczająco precyzyjna, aby ta właściwość mogła się utrzymać, biorąc pod uwagę, że używamy zmiennoprzecinkowych.
Benoît
@ Benoît Zawsze możesz użyć czeku i * i <= nzamiast, i <= sqrt(n)jeśli chcesz uniknąć zawiłości liczb zmiennoprzecinkowych.
Sven Marnach
348

Powiedzmy m = sqrt(n)więc m × m = n. Teraz, jeśli nnie jest liczbą pierwszą, nmożna ją zapisać jako n = a × btak m × m = a × b. Zauważ, że mjest to liczba rzeczywista n, aa bsą liczbami naturalnymi.

Teraz mogą być 3 przypadki:

  1. a> m ⇒ b <m
  2. a = m ⇒ b = m
  3. a <m ⇒ b> m

We wszystkich 3 przypadkach min(a, b) ≤ m. Dlatego jeśli szukamy do m, jesteśmy zmuszeni znaleźć co najmniej jeden czynnik n, który wystarczy, aby pokazać, że nnie jest liczbą pierwszą.

BiGYaN
źródło
4
n = 12 m = sqrt (12) = 3,46, a = 2, b = 6. n = m m, tj. 12 = 3,46 * 3,46 in = b b, tj. 12 = 2 * 6. Teraz warunek 3. a <m <b tj. 2 <3,46 <6. Aby sprawdzić liczbę pierwszą, musimy tylko sprawdzić liczbę mniejszą niż 3,46, czyli 2, aby dowiedzieć się, że liczba ta nie jest liczbą pierwszą. Dlatego sprawdź podzielność przez liczby mniejsze lub równe (jeśli n = 4, m = a = b = 2) pierwiastek kwadratowy z n.
anukalp
2
Myślę, że powinniśmy najpierw podkreślić to założenie. Załóż n is not a primei udowodnij, w przeciwnym razie jest to liczba pierwsza.
Huei Tan,
Właściwie nie jestem przekonany, że to lepsza odpowiedź. To poprawna odpowiedź, ale tak naprawdę nie odpowiada na pytanie. To tylko opisuje niektóre inne dynamiki wokół liczb pierwszych i sqrt. Odpowiedzi @ Svena są zwięzłe i nie tworzą więcej pytań.
Jon M
1
Cofnąłem się do ostatniej dobrej wersji. przegapiłeś to, gdy ktoś niepotrzebnie usunął słowo („stąd”), które jest potrzebne do przepływu.
Czy Ness
55

Ponieważ jeśli współczynnik jest większy niż pierwiastek kwadratowy z n, drugi czynnik, który pomnożyłby z nim wartość równą n, jest koniecznie mniejszy niż pierwiastek kwadratowy z.

patros
źródło
37

Bardziej intuicyjnym wyjaśnieniem byłoby:

Pierwiastek kwadratowy ze 100 wynosi 10. Powiedzmy, że axb = 100, dla różnych par a i b.

Jeśli a == b, to są one równe i są pierwiastkiem kwadratowym równym 100. Które wynosi 10.

Jeśli jeden z nich ma mniej niż 10, drugi musi być większy. Na przykład 5 x 20 == 100. Jeden jest większy niż 10, drugi jest mniejszy niż 10.

Myśląc o axb, jeśli jeden z nich spadnie, drugi musi stać się większy, aby zrekompensować, więc produkt pozostaje na 100. Obracają się wokół pierwiastka kwadratowego.

Pierwiastek kwadratowy z 101 wynosi około 10.049875621. Więc jeśli testujesz liczbę 101 pod kątem pierwszeństwa, musisz wypróbować liczby całkowite do 10, w tym 10. Ale same 8, 9 i 10 nie są liczbami pierwszymi, więc musisz przetestować tylko do 7, czyli główny.

Ponieważ jeśli istnieje para czynników z jedną z liczb większą niż 10, druga z pary musi być mniejsza niż 10. Jeśli mniejszy nie istnieje, nie ma pasującego większego współczynnika 101.

Jeśli testujesz 121, pierwiastek kwadratowy wynosi 11. Musisz przetestować pierwsze liczby całkowite od 1 do 11 (włącznie), aby sprawdzić, czy przejdzie ono równomiernie. 11 razy idzie 11 razy, więc 121 nie jest liczbą pierwszą. Jeśli zatrzymałeś się na 10, a nie testowałeś 11, straciłbyś 11.

Musisz przetestować każdą liczbę całkowitą większą niż 2, ale mniejszą lub równą pierwiastkowi kwadratowemu, zakładając, że testujesz tylko liczby nieparzyste.

`

Archit Garg
źródło
3
„Myśląc o axb, jeśli jeden z nich spadnie, drugi musi być większy, aby to zrekompensować, więc produkt pozostaje na 100. Obracają się wokół pierwiastka kwadratowego.” Moja chwila aha! Dziękuję Ci!
Brian Wigginton
To najlepsza odpowiedź.
JeanieJ
19

Załóżmy, że nnie jest liczbą pierwszą (większą niż 1). Są więc liczby ai btakie

n = ab      (1 < a <= b < n)

Przez pomnożenie relacji a<=bprzez ai botrzymujemy:

a^2 <= ab
 ab <= b^2

Dlatego: (zauważ, że n=ab)

a^2 <= n <= b^2

Stąd: (Zauważ, że ai bsą pozytywne)

a <= sqrt(n) <= b

Więc jeśli liczba (większa niż 1) nie jest liczbą pierwszą i testujemy podzielność aż do pierwiastka kwadratowego z liczby, znajdziemy jeden z czynników.

LoMaPh
źródło
8

Załóżmy, że podana liczba całkowita Nnie jest liczbą pierwszą,

Następnie N można factorized na dwa czynniki ai b, 2 <= a, b < Ntak, że N = a*b. Oczywiście oba z nich nie mogą być większe niż sqrt(N)jednocześnie.

Załóżmy bez utraty ogólności, która ajest mniejsza.

Jeśli nie możesz znaleźć dzielnika Nprzynależności w tym zakresie [2, sqrt(N)], co to oznacza?

Oznacza to, że Nnie ma dzielnika w [2, a]as a <= sqrt(N).

W związku z tym, a = 1i b = n, a więc z definicji Njest pierwszorzędna .

...

Dalsza lektura, jeśli nie jesteś zadowolony:

(a, b)Możliwe jest wiele różnych kombinacji . Powiedzmy, że są:

(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 ), ....., (a k , b k ). Bez straty ogólności zakładamy I <b I , 1<= i <=k.

Teraz, aby móc pokazać, że Nnie jest liczbą pierwszą, wystarczy pokazać, że żadnego z i nie można dalej rozkładać na czynniki. Wiemy również, że i <= sqrt(N)i dlatego musisz sprawdzić, do sqrt(N)którego pokrycia będzie wszystkie i . Odtąd będziesz mógł stwierdzić, czy Njest liczbą pierwszą.

...


źródło
7

To naprawdę tylko podstawowe zastosowania faktoryzacji i pierwiastków kwadratowych.

Może się to wydawać abstrakcyjne, ale w rzeczywistości polega po prostu na tym, że maksymalnym możliwym silnikiem liczby niepierwszej musiałby być pierwiastek kwadratowy, ponieważ:

sqrroot(n) * sqrroot(n) = n.

Biorąc pod uwagę, że jeśli dowolna liczba całkowita powyżej 1i poniżej lub w górę sqrroot(n)równomiernie dzieli się na n, to nnie może być liczbą pierwszą.

Przykład pseudokodu:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}
Super Cat
źródło
Genialna obserwacja. Wykorzystanie tej obserwacji do stworzenia guardinstrukcji w Swift w połączeniu z tym przydatnym stackoverflow.com/a/25555762/4475605 w celu wczesnego wyjścia z obliczeń zamiast marnowania mocy obliczeniowej. Dziękujemy za wysłanie.
Adrian
@Adrian Muszę wyznać, że po powrocie do tej odpowiedzi znalazłem błąd w momencie wysyłania wiadomości. Nie możesz wykonać dzielenia na 0 i teoretycznie, gdybyś mógł ++istać się liczbą 1, która zawsze zwróciłaby wartość false (ponieważ 1 dzieli się na wszystko). Poprawiłem powyższą odpowiedź.
Super Cat,
Tak ... zająłem się tym w moim kodzie ... twoja obserwacja pierwiastka kwadratowego jest świetnym sposobem na wyrzucenie wartości innej niż pierwotna na początku przed rozpoczęciem obliczeń. Zostałem zabity dużą liczbą, która okazała się stratą czasu. Dowiedziałem się również, że ten algorytm może znacznie skrócić czas przetwarzania dużych liczb. en.wikipedia.org/wiki/Miller –Rabin_primality_test
Adrian
6

Aby sprawdzić, czy liczba N jest liczbą Prime, czy nie. Musimy tylko sprawdzić, czy N można podzielić przez liczby <= SQROOT (N). Wynika to z faktu, że jeśli weźmiemy N na dowolne 2 czynniki, powiedzmy X i Y, tj. N = X Y. Każdy z X i Y nie może być mniejszy niż SQROOT (N), ponieważ wtedy X Y <N Każdy z X i Y nie może być większy niż SQROOT (N), ponieważ wtedy X * Y> N

Dlatego jeden czynnik musi być mniejszy lub równy SQROOT (N) (podczas gdy drugi czynnik jest większy lub równy SQROOT (N)). Aby więc sprawdzić, czy N jest liczbą pierwszą, musimy tylko sprawdzić te liczby <= SQROOT (N).

Rhea Rodrigues
źródło
3

Powiedzmy, że mamy liczbę „a”, która nie jest liczbą pierwszą [nie liczba pierwsza / liczba zespolona oznacza - liczbę, którą można podzielić równomiernie przez liczby inne niż 1 lub sama. Na przykład 6 można podzielić równomiernie przez 2 lub 3, a także przez 1 lub 6].

6 = 1 × 6 lub 6 = 2 × 3

Jeśli więc „a” nie jest liczbą pierwszą, można ją podzielić przez dwie inne liczby i powiedzmy, że te liczby to „b” i „c”. Co znaczy

a = b * c.

Teraz, jeśli „b” lub „c”, którykolwiek z nich jest większy niż pierwiastek kwadratowy z „a”, to mnożenie „b” i „c” będzie większe niż „a”.

Zatem „b” lub „c” jest zawsze <= pierwiastek kwadratowy z „a”, aby udowodnić równanie „a = b * c”.

Z powyższego powodu, gdy testujemy, czy liczba jest liczbą pierwszą, czy nie, sprawdzamy tylko do pierwiastka kwadratowego z tej liczby.

Abu Naser Md Shoaib
źródło
1
b & c <= Math.sqrt (n) ?; Powinien to być raczej b || c (b lub c), ponieważ jeśli n = 6, b = 3, c = 2, to Math.sqrt (n)> c.
daGo
Dzięki kolego za korektę. robić korektę. :)
Abu Naser Md Shoaib
2

Biorąc pod uwagę dowolną liczbę n, jednym ze sposobów na znalezienie jej czynników jest uzyskanie pierwiastka kwadratowego p:

sqrt(n) = p

Oczywiście, jeśli pomnożymy pprzez siebie, wówczas otrzymamy n:

p*p = n

Można go ponownie zapisać jako:

a*b = n

Gdzie p = a = b. Jeśli awzrasta, bzmniejsza się, aby utrzymać a*b = n. Dlatego pjest górną granicą.

Aktualizacja: Dzisiaj ponownie czytam tę odpowiedź i stała się dla mnie bardziej zrozumiała. Wartość pniekoniecznie oznacza liczbę całkowitą, ponieważ jeśli tak, to nnie byłaby liczbą pierwszą. Tak, pmoże być prawdziwy numer (tj z frakcji). I zamiast przejść przez cały zakres n, teraz musimy tylko przejść przez cały zakres p. Drugi pto kopia lustrzana, więc w efekcie zmniejszamy zasięg o połowę. A potem, teraz widzę, że faktycznie możemy kontynuować przerabianie square rooti robienie tego, paby zwiększyć połowę zakresu.

trueadjustr
źródło
1

Niech n nie będzie liczbą pierwszą. Dlatego ma co najmniej dwa czynniki całkowite większe niż 1. Niech f będzie najmniejszym z tych czynników n. Załóżmy, że f> sqrt n. Zatem n / f jest liczbą całkowitą LTE sqrt n, a więc mniejszą niż f. Dlatego f nie może być najmniejszym czynnikiem n. Reductio ad absurdum; najmniejszym czynnikiem n musi być LTE sqrt n.

Reb.Cabin
źródło
1

Każda liczba złożona jest iloczynem liczb pierwszych.

Powiedzmy n = p1 * p2, gdzie p2 > p1i gdzie są liczbami pierwszymi.

Jeśli n % p1 === 0wtedy n jest liczbą złożoną.

Jeśli n % p2 === 0tak, zgadnij co n % p1 === 0!

Nie ma więc mowy, że jeśli, n % p2 === 0ale n % p1 !== 0w tym samym czasie. Innymi słowy, jeśli liczbę zespoloną n można podzielić równomiernie przez p2, p3 ... pi (jej większy współczynnik), należy ją również podzielić przez jej najniższy współczynnik p1 . Okazuje się, że najniższy czynnik p1 <= Math.square(n)jest zawsze prawdziwy.

mieszaniec
źródło
Jeśli zastanawiasz się, dlaczego to prawda, @LoMaPh wyjaśnił ten fakt w swojej odpowiedzi. Dodałem swoją odpowiedź, ponieważ miałem naprawdę ciężkie problemy z wizualizacją i zrozumieniem innych udzielonych odpowiedzi. Po prostu nie kliknęło.
daGo
0

Aby przetestować pierwotność liczby, n , należy oczekiwać pętli, takiej jak:

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

Powyższa pętla robi to: dla danego 1 <i <n sprawdza, czy n / i jest liczbą całkowitą (pozostawia resztę 0). Jeśli istnieje znak i, dla którego n / i jest liczbą całkowitą, możemy być pewni, że n nie jest liczbą pierwszą, w którym to momencie pętla się kończy. Jeśli dla nie i, n / i jest liczbą całkowitą, to n jest liczbą pierwszą.

Jak w przypadku każdego algorytmu, pytamy: czy możemy zrobić lepiej?

Zobaczmy, co się dzieje w powyższej pętli.

Sekwencja i idzie: i = 2, 3, 4, ..., n-1

Kolejność sprawdzania liczb całkowitych jest następująca: j = n / i, czyli n / 2, n / 3, n / 4, ..., n / (n-1)

Jeśli dla niektórych i = a, n / a jest liczbą całkowitą, to n / a = k (liczba całkowita)

lub n = ak, wyraźnie n> k> 1 (jeśli k = 1, to a = n, ale nigdy nie osiąga n; a jeśli k = n, to a = 1, ale i zaczyna formę 2)

Ponadto, n / k = a, i jak stwierdzono powyżej, a jest wartością i więc n> a> 1.

Zatem a i k są liczbami całkowitymi od 1 do n (wyłączne). Ponieważ osiągam każdą liczbę całkowitą w tym zakresie, przy pewnej iteracji i = a, a przy innej iteracji i = k. Jeśli test pierwotności n nie powiedzie się dla min (a, k), to również nie powiedzie się dla max (a, k). Musimy więc sprawdzić tylko jeden z tych dwóch przypadków, chyba że min (a, k) = max (a, k) (gdzie dwa sprawdzenia zmniejszają się do jednego) tj. A = k, w którym punkcie a * a = n, które implikuje a = sqrt (n).

Innymi słowy, gdyby test pierwszeństwa n nie powiódł się dla niektórych i> = sqrt (n) (tj. Max (a, k)), to również nie powiedzie się dla niektórych i <= n (tj. Min (a , k)). Wystarczyłoby uruchomić test dla i = 2 do sqrt (n).

Aroonalok
źródło
W komentarzach i 6-letnich odpowiedziach jest wiele krótszych i IMHO dużo łatwiejszych do zrozumienia i bardziej szczegółowych wyjaśnień na temat ...
Thierry Lathuille,