DM n°3

[Amandine]

Bonjour,
J'ai un Dm de maths à faire, et je suis bloquée au dernier exercice. j'espère donc que vous pourrez m'aider

Voici l'exercice :
Ecrire un algorithme qui permet de compter le nombre de nombres premiers inférieurs ou égal à un entier n donné.

J'ai commencé mes recherches. Si j'ai bien compris il faut que je fasse un algorithme où au début on choisit une valeur n. Une fois que cette valeur est choisit l'algorithme doit tourner jusqu’à ce que la valeur X soit égal à N, tout en comptant les nombres premiers qu'il y a jusqu’à la valeur n. Je pense avoir compris comment fonctionne l'algorithme a peu près mais je ne sais pas comment faire pour que l'algorithme compte les nombres premiers car pour ça il faut encore qu'il les reconnaissent. Je suis donc bien embêté car je n'arrive pas à avancer.
J'espère que vous pourrez m'apporter votre aide.
En vous remerciant d'avance, bonne après-midi.
Amandine

[SoS-Math(25)]

Bonjour Amandine,

Tu as raison, il faut qu'il les reconnaissent.

Si k est ta variable qui va de 1 à n (ou plutôt de 2 à n car 1 n'est pas premier...) alors quelles conditions peux-tu tester sur k pour savoir s'il est premier ou non ?

Bon courage !

[Amandine]

Bonsoir,
Tout d'abord merci pour votre aide, j'ai une autre question du coup.
Et bien il faut que le nombre soit divisible par un nombre et que le résultat soit un entier pour qu'il soit premier.
C'est ce qu'il faut que je teste sur k.
Toutefois il faut que je puisse formuler ça de façon à ce que ceci rentre dans l'algorithme, et j'ai un peu de mal.
Merci d'avance pour votre réponse
Bonne soirée
Amandine

[SoS-Math(25)]

Et bien il faut que le nombre soit divisible par un nombre et que le résultat soit un entier pour qu'il soit premier.

Un nombre premier est un nombre qui n'est divisible que par 1 et par lui-même, donc pas divisible par d'autres nombres que ces deux là.

le gros du problème est donc effectivement de savoir si k (qui parcourt 2 jusqu'à n) est un nombre premier.

Il y a plusieurs façon plus moins optimales ou compliquées.

Une indication en français :

Si k est divible par 2 ou par 3 ou par .... alors ce n'est pas un nombre premier, sinon, il est premier.

Bon courage !