Tester la primalité d'un entier jusqu'à 10⁶

Lire un entier et déterminer s'il est premier, en utilisant un algorithme efficace adapté à la plage 1 à 10⁶.

25 minPublié le 20 mai 2026Proposé par Anonyme

Défi

// Lisez attentivement, codez sur votre machine

Énoncé

Le programme lit un entier N sur l'entrée standard et affiche PREMIER si N est un nombre premier, NON PREMIER sinon. Un nombre premier est un entier supérieur ou égal à 2 divisible uniquement par 1 et par lui-même. L'algorithme doit fonctionner efficacement jusqu'à N = 10⁶ (test par division jusqu'à √N suffit).

Contraintes

1 ≤ N ≤ 1 000 000.
1 n'est pas premier.
La complexité attendue est O(√N).
Afficher exactement PREMIER ou NON PREMIER, sans texte supplémentaire.
Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard.

Exemple

Entrée : 997
Sortie : PREMIER

Entrée : 1000000
Sortie : NON PREMIER

Espace solution

Proposer une solution

Connectez-vous ou créez un compte pour envoyer votre code (aucune exécution côté serveur — on stocke juste le texte pour la communauté).

Se connecter Créer un compte

Défi précédentTester si un entier est pair ou impair Défi suivant Interface Utilisateur avec champs optionnels

// À garder en tête

D'abord, faire marcher
On ne cherche pas à optimiser : d'abord, on fait marcher le truc. Optimiser vient ensuite — et ça aussi, ça s'apprend. (Si un défi porte sur l'optimisation, son énoncé le précise.)
Pas de mauvaise réponse
Il n'y a pas de mauvaise réponse à un défi. Le but, c'est de le faire. Ce qui compte, c'est de s'entraîner.
Trop dur ? Au suivant
Un défi te résiste ? N'hésite pas à en prendre un autre. Ils seront encore là demain.