Perché controlliamo fino alla radice quadrata di un numero primo per determinare se è primo?

StackOverflow https://stackoverflow.com/questions/5811151

Domanda

Per verificare se un numero è primo o no, perché dobbiamo verificare se esso è divisibile solo fino alla radice quadrata di tale numero?

È stato utile?

Soluzione

Se un numero n non è un numero primo, esso può essere scomposto in due fattori a e b: 

n = a * b

Se sia a e b erano superiori alla radice quadrata di n, allora a * b sarebbe maggiore di n. Così almeno uno di questi fattori deve essere inferiore o uguale alla radice quadrata di n, e se non riusciamo a trovare nessuna fattori inferiore o uguale alla radice quadrata, n deve essere privilegiata.

Altri suggerimenti

diciamo m = sqrt(n) Let poi m × m = n. Ora, se n non è un n allora primo può essere scritta come n = a × b, così m × m = a × b. Si noti che m è un numero reale, mentre n, a e b sono numeri naturali.

Ora ci può essere di 3 casi:

  1. a> m ? b
  2. a = m ? b = m
  3. un m

In tutti i 3 casi, min(a, b) ≤ m. Quindi, se si cerca fino m, siamo destinati a trovare almeno un fattore di n, che è sufficiente a dimostrare che n non è primo.

Perché se un fattore è maggiore della radice quadrata di n, l'altro fattore che avrebbe moltiplicato con esso per uguale n è necessariamente inferiore alla radice quadrata di n.

Una spiegazione più intuitiva potrebbe essere: -

La radice quadrata di 100 è 10. Let dire un x b = 100, per diverse coppie di ae b.

Se a == b, allora sono uguali, e sono la radice quadrata di 100, esattamente. Che è 10.

Se uno di loro è inferiore a 10, l'altro deve essere maggiore. Ad esempio, 5 x 20 == 100. Uno è maggiore di 10, l'altro è inferiore a 10.

Pensando a x b, se uno di loro scende, l'altro deve diventare più grande per compensare, in modo che i soggiorni di prodotto a 100. Essi ruotano attorno alla radice quadrata.

La radice quadrata di 101 è circa 10,049,875621 millions. Quindi, se si sta testando il numero 101 per primalità, avete solo bisogno di provare i numeri interi fino a 10, comprese le 10. Ma 8, 9, e 10 non si sono primi, in modo da avere solo per testare fino a 7, che è Prime.

Perché se c'è una coppia di elementi con uno dei numeri maggiori di 10, l'altro della coppia deve essere inferiore a 10. Se il secondario non esiste, non c'è più grande fattore corrispondenza di 101.

Se si sta testando 121, la radice quadrata è 11. È necessario testare gli interi primi da 1 a 11 (compreso) per vedere se va in modo uniforme. 11 va a 11 volte, in modo da 121 non è primo. Se si era fermato a 10, e non testato 11, si sarebbe perso 11.

È necessario testare ogni numero intero maggiore privilegiata di 2, ma inferiore o uguale alla radice quadrata, supponendo che si sta solo testando i numeri dispari.

`

n Supponiamo che non è un numero primo (maggiore di 1). Quindi ci sono numeri a e b tali che 

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

Moltiplicando il a<=b relazione da a e b otteniamo: 

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

Quindi: (notare che n=ab) 

a^2 <= n <= b^2

Quindi: (Notare che a e b sono positivi) 

a <= sqrt(n) <= b

Quindi, se un numero (maggiore di 1) non è primo e ci prova di divisibilità fino a radice quadrata del numero, troveremo uno dei fattori.

E 'tutti gli usi in realtà solo di base di fattorizzazione e Piazza Roots.

Può sembrare di essere astratto, ma in realtà è semplicemente risiede nel fatto che la massima fattoriale possibile un non-prime-numero avrebbe dovuto essere la sua radice quadrata perché:

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

Posto che, se un numero intero sopra 1 e sotto o fino a sqrroot(n) divisibile per n , quindi n non può essere un numero primo.

Pseudo-codice di esempio: 

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

di lasciare supporre che la data N intero non è primo,

Poi N può essere fattorizzata in due fattori a e b, 2 <= a, b < N tale che N = a*b. Chiaramente, entrambi non può essere maggiore di sqrt(N) simultaneamente.

Supponiamo senza perdita di generalità che a è più piccolo.

Ora, se non si poteva trovare qualsiasi divisore di N appartenenza nella gamma [2, sqrt(N)], che cosa significa?

Ciò significa che N non ha alcun divisore [2, a] come a <= sqrt(N).

Pertanto, a = 1 e b = n e quindi Per definizione, N è primo .

...

Ulteriore lettura, se non siete soddisfatti:

Molte diverse combinazioni di (a, b) può essere possibile. Diciamo che sono:

(a 1 , b 1 ), (a 2 , b 2 ), (a < sub> 3 , b 3 ), ....., (a k , b k ). Senza perdita di generalità, assumere una i i , 1<= i <=k.

Ora, per essere in grado di dimostrare che N non è primo, è sufficiente a dimostrare che nessuno di un i può essere Factorized ulteriormente. E sappiamo anche che un i <= sqrt(N) e quindi è necessario controllare fino sqrt(N) che coprirà tutto un i . E quindi si sarà in grado di concludere o meno N è primo.

...

Quindi, per verificare se un numero N è primo o no. Dobbiamo controllare solo se N è divisibile per il numero <= sqroot (N). Questo perché, se fattore N in nessuna 2 fattori dire X e Y, cioè. N = X Y. Ciascuno di X e Y non può essere inferiore a sqroot (N) perché poi, X Y N

dunque un fattore deve essere inferiore o uguale a sqroot (N) (mentre l'altro fattore è maggiore o uguale a sqroot (N)). Quindi, per verificare se N è primo abbiamo bisogno controlliamo solo quei numeri <= sqroot (N).

diciamo Let abbiamo un numero "A", che non è primo [Not Prime / mezzo numero composto - un numero che può essere diviso equamente da numeri diversi da 1 o se stesso. Ad esempio, 6 può essere suddivisa in modo uniforme da 2, o 3, nonché da 1 o 6].

6 = 1 × 6 o 6 = 2 × 3

Così ora se "a" non è primo allora può essere diviso per altri due numeri e diciamo che questi numeri sono "b" e "c". Il che significa

a = b * c.

Ora se "b" o "c", uno di essi è maggiore di radice quadrata di "a" della moltiplicazione di 'b' e 'c' sarà maggiore 'a'.

Quindi, "b" e "c" è sempre <= radice quadrata di "a" per dimostrare l'equazione "a = b * c".

A causa della ragione sopra, quando si controlla se un numero è primo o no, controlliamo solo fino radice quadrata di tale numero.

Sia n non-prime. Pertanto, esso ha almeno due fattori intero maggiore di 1. Sia f più piccolo di tali fattori di n. Supponiamo che f> sqrt n. Allora n / f è un numero intero sqrt LTE n, così piccolo di f. Pertanto, f non può essere il fattore più piccolo di n. Reductio ad absurdum; il fattore più piccolo di n deve essere LTE sqrt n.

Dato un qualsiasi numero n, quindi un modo per trovare i suoi fattori è quello di ottenere la sua p radice quadrata: 

sqrt(n) = p

Naturalmente, se moltiplichiamo p di per sé, allora otteniamo n indietro: 

p*p = n

Può essere riscritto come: 

a*b = n

Dove p = a = b. Se aumenta a, quindi b diminuisce per mantenere a*b = n. Pertanto, p è il limite superiore.

Per testare la primalità di un numero, n , ci si aspetterebbe un ciclo, come segue, in primo luogo: 

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

Nei ciclo precedente non è questo: per un dato 1 , esso controlla se n / i è un numero intero (foglie resto 0). Se esiste un i per cui n / i è un numero intero, possiamo essere sicuri che n non è un numero primo, a questo punto il ciclo termina. Se non i, n / i è un intero, allora n è primo.

Come per ogni algoritmo, ci chiediamo:? Possiamo fare meglio

Vediamo cosa sta succedendo nel ciclo sopra.

La sequenza di i va: i = 2, 3, 4, ..., n-1

E la sequenza di interi verifiche va: j = n / i, che è n / 2, n / 3, n / 4, ..., n / (n-1)

Se per qualche i = a, n / a è un numero intero, allora n / a = k (intero)

o n = ak, chiaramente n> k> 1 (se k = 1, allora a = n, ma i non raggiunge mai n, e se k = n, allora a = 1, ma i inizia modulo 2)

Inoltre, n / k = a, e, come detto sopra, a è un valore dei così n> a> 1.

Quindi, a e k sono entrambi numeri interi compresi tra 1 e n (esclusiva). Poiché, i raggiunge ogni intero in tale intervallo, in qualche iterazione i = a, e in qualche altro iterazione i = k. Se il test di primalità di n non riesce per min (a, k), sarà anche fallire per max (a, k). Quindi abbiamo bisogno di controllare solo uno di questi due casi, a meno che min (a, k) = max (a, k) (dove due controlli riducono a uno) vale a dire, a = k, a quel punto a * a = n, che implica a = sqrt (n).

In altre parole, se il test di primalità di n non dovesse per qualche i> = sqrt (n) (cioè, max (a, k)), allora sarebbe anche sicuro per qualche i <= n (cioè, min (a, k)). Quindi, sarebbe sufficiente se corriamo il test per i = 2 a sqrt (n).

Qualsiasi numero composto è un prodotto di numeri primi.

diciamo n = p1 * p2, dove p2 > p1 e sono numeri primi.

Se n % p1 === 0 allora n è un numero composto.

Se n % p2 === 0 quindi indovinate un po 'n % p1 === 0 così!

Quindi, non c'è modo che se n % p2 === 0 ma n % p1 !== 0 allo stesso tempo. In altre parole, se un numero composto n può essere diviso uniformemente p2, p3 ... pi (il suo fattore di maggiore) deve essere diviso per il suo fattore più basso p1 anche. Si scopre che il fattore più basso p1 <= Math.square(n) è sempre vero.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top