Znajdź numer główny?

Question

Aby ustalić, czy N jest liczbą pierwszą, wystarczy wyszukać wszystkie liczby mniejsze lub równe sqrt (N). Dlaczego? Piszę kod C, więc próbuję zrozumieć przyczynę tego.

Answer 1

N jest liczbą pierwszą, jeśli jest dodatnia, która jest podzielna przez dokładnie dwóch liczb całkowitych dodatnich, 1 i N. Ponieważ liczba jest dzielników nie może być większa niż tej liczby, co prowadzi do prostego testu pierwszości:

• Jeśli liczba całkowita N, większa niż 1, nie jest podzielna przez żadną liczbę całkowitą z zakresu [2, N-1], to N jest liczbą pierwszą. W przeciwnym razie N nie jest liczbą pierwszą.

Jednak byłoby miło zmodyfikować ten test, aby był szybszy. Zbadajmy więc.

Należy zauważyć, że dzielniki N występują w parach. Jeśli N jest podzielna przez liczbę M, to jest również podzielna przez N/M. Na przykład 12 jest dzielone przez 6, a więc także przez 2. Ponadto, jeśli M >= sqrt(N), to N/M <= sqrt(N).

Oznacza to, że jeśli liczby nie mają wartości mniejszej lub równej sqrt (N) dzielą N, liczby większe niż sqrt (N) dzielą N (oprócz samych 1 i N), w przeciwnym razie powstanie sprzeczność.

Więc mamy lepszą Test:

• Jeśli liczbą całkowitą N, większy niż 1, nie jest podzielna przez dowolną liczbę całkowitą w zakresie [2, sqrt(N)], następnie N jest liczbą pierwszą. W przeciwnym razie N nie jest liczbą pierwszą.

Jeśli weźmiesz pod uwagę powyższe rozumowanie, powinieneś zauważyć, że liczba, która przejdzie ten test, również przechodzi pierwszy test, a numer, który nie przejdzie tego testu, również nie przejdzie pierwszego testu. Testy są zatem równoważne.

Answer 2

Liczba zespolona (jedna, która nie jest pierwsza, lub 1) ma co najmniej 1 parę czynników i jest gwarantowana, że ​​jedna z liczb z każdej pary jest mniejsza niż lub równa pierwiastkowi kwadratowemu liczby (o co pytasz).

Jeśli wyrównasz pierwiastek kwadratowy liczby, otrzymasz sam numer (sqrt(n) * sqrt(n) = n), więc jeśli zrobiłeś jedną z liczb większych (niż sqrt(n)), musiałbyś zmniejszyć drugi. Jeśli następnie sprawdzisz tylko liczby od 2 do sqrt(n), sprawdziłeś wszystkie możliwe czynniki, ponieważ każdy z tych czynników zostanie sparowany z liczbą większą niż sqrt(n) (z wyjątkiem oczywiście, jeśli liczba jest w rzeczywistości kwadratem niektórych inna liczba, np. 4, 9, 16 itd. ... ale to nie ma znaczenia, ponieważ wiesz, że nie są pierwszymi, są one łatwo uwzględniane same w sobie przez sqrt(n)).

Answer 3

Ponieważ w najgorszym przypadku numer n można wyrazić jako .

Jeśli liczba może być wyrażona w sposób różny, mężczyźni, że jeden z dzielników będzie mniejszy niż a = sqrt(n), ale drugi może być większy.

Answer 4

Powód jest prosty, każda liczba większa niż sqrt spowoduje, że drugi mnożnik będzie mniejszy niż sqrt. W takim przypadku powinieneś już to sprawdzić.

Answer 5

Niech n = x b się kompozyt.

Załóżmy > sqrt (n) i b> sqrt (n).

x b> sqrt (n) x sqrt (n)

x b>n

Ale wiemy × b = n zatem < sqrt (n) lub b < sqrt (n).

Ponieważ trzeba tylko wiedzieć lub b pokazać n jest złożona, tylko trzeba sprawdzić numery do sqrt (n), aby znaleźć taki numer.