Bonsoir Natty,
Alors dans un premier temps, on sait qu'on peut arrêter les test lorsqu'on arive à un nombre premier qui est supérieur ou égale à n/2 pour montrer que n est premier. Ceci est plus simple à voir car si on considère un nombre premier plus grand que n/2, on peut voir que n/2>n/(n/2)>2. Et par conséquent, le resultat de la division sera forcément un nombre entre 2 et n/2 qu'on a donc déjà testé!
Maintzenant, on peut en effet faire mieux en disant qu'on peut arrêter les tests lorsqu'on a testé tous les nombres premiers inférieurs ou égale à √n. C'est à dire que si on testait un nombre supérieur à √n, nous pouvons affirmer qu'il ne divisera pas n.
Alors comment voir cela?
Supposons que n=p*q
Par conséquent, si on suppose que p et q sont supérieurs strictement à √n (tous les deux!) alors p*q>n
Contradiction car p*q=n
Par conséquent, p ou q est inférieur ou égale à √n. Donc il existe un diviseur premier de p par exemple qui divisera donc n.
En conclusion, il suffit de tester la divisibilité des nombres premiers inférieurs ou égaux à √n.
Est-ce que c'est plus claire ainsi?
Bon courage!
Dim 6 Déc - 18:41
