Dlaczego sprawdzamy pierwiastek kwadratowy liczby pierwszej, aby określić, czy jest ona pierwsza?

Powiedzmy m = sqrt(n) wtedy m × m = n. Jeśli n nie jest liczbą pierwszą, to n można zapisać jako n = a × b, więc m × m = a × b. Zauważ, że m jest liczbą rzeczywistą, podczas gdy n, a i {[9] } są liczbami naturalnymi.

Teraz mogą być 3 przypadki:

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

We wszystkich 3 przypadkach, min(a, b) ≤ m. Dlatego jeśli poszukamy do m, musimy znaleźć przynajmniej jeden czynnik n, który wystarczy, aby pokazać, że n nie jest prime.

Ponieważ jeśli czynnik jest większy niż pierwiastek kwadratowy n, to drugi czynnik, który mnoży się z nim do równego n, jest koniecznie mniejszy niż pierwiastek kwadratowy N.

Bardziej intuicyjne Wyjaśnienie byłoby: -

Pierwiastek kwadratowy z 100 wynosi 10. Załóżmy, że A x b = 100, dla różnych par a i b.

Jeśli a = = b, to są równe i są pierwiastkiem kwadratowym z 100, dokładnie. Czyli 10.

Jeśli jeden z nich jest mniejszy 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 x b, jeśli jeden z nich upadnie, drugi musi się powię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 na prymat, musisz tylko spróbować liczby całkowitej do 10, w tym 10. Ale 8, 9 i 10 nie są same w sobie prime, więc trzeba tylko przetestować do 7, który jest prime.

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

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

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

`

Załóżmy, że n nie jest liczbą pierwszą (większą niż 1). Istnieją więc liczby a i b takie, że

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

Mnożąc relację a<=b przez a i b otrzymujemy:

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

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

a^2 <= n <= b^2

Stąd: (zauważ, że a i b są dodatnie)

a <= sqrt(n) <= b

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

Załóżmy, że dana liczba całkowita N nie jest liczbą pierwszą,

Wtedy N można podzielić na dwa czynniki a i b , 2 <= a, b < N takie, że N = a*b. Najwyraźniej oba nie mogą być większe niż sqrt(N) jednocześnie.

Załóżmy bez utraty ogólności, że a jest mniejsza.

Oznacza to, że N nie ma żadnego dzielnika w [2, a] jako a <= sqrt(N).

Zatem, a = 1 i b = n i stąd z definicji, N jest liczbą pierwszą .

...

Dalsze czytanie jeśli nie jesteś zadowolony:

Wiele różnych kombinacji (a, b) może być możliwe. Powiedzmy, że są:

(a₁, b₁), (a₂, b₂), (a₃, b₃), ..... , (A_k, b_k ). Bez utraty ogólności, Załóżmy _i i, 1<= i <=k.

Teraz, aby móc pokazać, żeN nie jest pierwsza, wystarczy pokazać, że żaden z _i nie może być dalej faktorowany. I wiemy też, że A _isqrt(N) i dlatego musisz sprawdzić do sqrt(N), które obejmie wszystkie _i . I stąd będziesz mógł stwierdzić, czy N jest liczbą pierwszą.

...

To tylko podstawowe zastosowania faktoryzacji i pierwiastków kwadratowych.

Może wydawać się abstrakcyjny, ale w rzeczywistości po prostu polega na tym, że maksymalna możliwa czynnikowa liczba niepierwsza musi być pierwiastkiem kwadratowym, ponieważ:

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

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

Pseudo-kod przykład:

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 pierwsza, czy nie. Musimy tylko sprawdzić, czy N jest podzielne przez liczby Y. Każdy z X i Y nie może być mniejszy 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)). Więc aby sprawdzić, czy N is Prime musimy tylko sprawdzić te liczby

Załóżmy, że mamy liczbę "a", która nie jest liczbą pierwszą [oznacza liczbę pierwszą/złożoną - liczbę, którą można podzielić równomiernie przez liczby inne niż 1 lub samą siebie. Na przykład 6 można podzielić równomiernie przez 2, lub przez 3, a także przez 1 lub 6].

6 = 1 × 6 or 6 = 2 × 3

Więc teraz, Jeśli " a "nie jest liczbą pierwszą, to można ją podzielić przez dwie inne liczby i powiedzmy, że te liczby to" b " I "c". Co oznacza

A=b * c.

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

Więc, " b " i " c " jest zawsze

Z powyższego powodu, kiedy testujemy, czy liczba jest pierwsza, czy nie, sprawdzamy tylko do pierwiastka kwadratowego tej liczby.

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

Aby sprawdzić pierwotność liczby, n , można oczekiwać pętli, takiej jak następująca w pierwszej kolejności:

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 sprawdza, czy n / i jest liczbą całkowitą (pozostawia resztę 0). Jeśli istnieje i, dla którego n / i jest liczbą całkowitą, to możemy być pewni, że n nie jest liczbą pierwszą, w którym to momencie pętla kończy się. Jeśli dla no i, n / i jest liczbą całkowitą, to n jest liczbą pierwszą.

Jak przy każdym algorytmie, pytamy : Czy możemy stać się lepsi ?

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

Ciąg i idzie : i = 2, 3, 4,... , n-1

I Sekwencja sprawdzeń całkowitych idzie : 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ągnę n; A jeśli k = n, to a = 1, ale zaczynam formę 2)

Również, n / k = a, i jak stwierdzono powyżej, a jest wartością i so N > a > 1.

Zatem a i k są liczbami całkowitymi między 1 A N (exclusive). Ponieważ i dociera do każdej liczby całkowitej w tym zakresie, przy pewnej iteracji i = A, a przy innej iteracji i = K. jeśli test pierwszości N zawiedzie dla min( A, k), to również zawiedzie 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 kontrole zmniejszają się do jednego), tj. a = k, w którym punkcie a*a = n, co implikuje a = sqrt (n).

Innymi słowy, jeśli test pierwszości n miał zawieść dla niektórych i > = sqrt(n) (tj. max(a, k)), a następnie również zawieść dla niektórych I

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

sqrt(n) = p

Oczywiście, jeśli mnożymy p przez siebie, to wracamy n:

p*p = n

Można go zapisać ponownie jako:

a*b = n

Gdzie p = a = b. Jeśli a wzrasta, to b maleje, aby utrzymać a*b = n. Dlatego p jest górną granicą.