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

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

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

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

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.

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.

`

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.

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 ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ....., (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ą.

...

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

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

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.

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.

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.

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.

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