Déterminer si un nombre est premier

Déterminer si un nombre est premier est un problème complexe. Il est aussi très sensible dans la mesure ou les systèmes de cryptographie utilisés pour sécuriser les transactions sur Internet utilisent les nombres premiers. Cela dit, les nombres utilisés possèdent plusieurs centaines de chiffres ! ! !

Néanmoins pour des petits nombres, un algorithme naïf peut tout à fait suffire. L'idée est de regarder la divisibilité par tous les nombres premiers inférieurs à la racine carrée du nombre à tester.

Question

391 est-il premier ?

Indice

On testera d'abord les critères de divisibilité par 2, 3, 5, 9 au cas ou...

Solution

\(\sqrt {391}\approx 19,7\) donc on va regarder la divisibilité de 391 par 2, 3, 5, 7, 11, 13, 17 et 19

\(391 = 17\times 23\) donc 391 n'est pas premier

Question

397 est-il premier ?

Indice

On testera d'abord les critères de divisibilité par 2, 3, 5, 9 au cas ou...

Solution

\(\sqrt {397}\approx 19,9\) donc on va regarder la divisibilité de 391 par 2, 3, 5, 7, 11, 13, 17 et 19

Cette fois-ci on constate qu'aucun nombre premier inférieur à 19 ne divise 397, donc 397 est un nombre premier.