Liste des nombres premier

Soyez le premier à donner votre avis sur cette source.

Vue 5 449 fois - Téléchargée 153 fois

Description

Liste des nombres premier de 3 à 101 ...........

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Viper31
Messages postés
96
Date d'inscription
mardi 2 avril 2002
Statut
Membre
Dernière intervention
7 août 2005
-
il me semble que si un chiffre n'est pas premier , donc si il admet un diviseur , il y en a forcement un autre (donc 2 diviseur en plus de 1 et lui meme) . style 10 n'est pas premier car divisible par 5 ET 2 , (81=9*9=27*3) , ya une sorte de """"symetrie"""" (vous avez noté les gros guillemet ^^) des diviseurs.

et donc si il est pas premier , il admet forcement 1 (ou plus) diviseur entre 2 et la moitie de lui meme.

donc pour simplifier ta boucle , tu pourrai juste tester de diviser par 2 puis par tout les impairs suivant jusqu'a la moitie du nombre car si il est divisible par 4 , il est aussi par 2 donc ca sert a rien de tester les autres nombres pair ;) .

comme ca t'optimise ^^ et tu peux faire beaucoup plus de chiffre :p !!
et donc ca t obligerai a monter les diviseurs successif dans ta boucle interne et lieu de descendre (d=d+2 au lieu de d--) ,

mais il me semble que pour avoir la liste de n premier nb premier, ya un algo encore plus simple je crois ! je chercherai dans mes cours ^^ ...

tiens j'ai encore mieux pour ton algo , style dans ta premiere boucle , tu saute direct tout les pair et basta ... for (n=3 ; n < 1001 ; n=n+2). comme ca tu te fais pas chier a diviser par 2 ^^

le gros probleme de ton code (pas visible a un si petit niveau de bouclage) c'est que tu test absolument tout les cas alors que certain sont inutiles car previsible , donc style si tu voulais avoir tout les nombres premiere jusqua 1 million , compare le temps que met ton algo et celui que je te conseil ...

@++
cs_Velu
Messages postés
1
Date d'inscription
samedi 5 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
-
en fait, il suffit de chercher par les nombres premiers inférieurs à la racine carrée du nombre que l'on cherche ;o)
En effet, si un nombre n est divible par a, il sera divisible par n/a. Et parmis a et n/a, il y en a forcement un inférieur à la racine carrée de n ;o)
Et si un nombre non premier est divisible par un nombre non-premier, il sera aussi divisible par les nombres premiers qui composent ce non-premier.
Mais il faut alors stocker les nombres premiers et les recuperer pour les division, et en terme de temps, je ne pense pas qu'on y gagne sur les 101 nombre premiers . C'est sur les tres grand snombres que c'est important.
Mais au moins, dans ce cas : 2 et le snombres impairs jusqu'à la racine carrée du nombre me semble une bonne solution. Et même mieux que 2 : plutôt que de vérifier si un nombre est divisible par 2, pourquoi ne pas faire la vérification seulement sur les nombre impairs ? :o)
BlackGoddess
Messages postés
338
Date d'inscription
jeudi 22 août 2002
Statut
Membre
Dernière intervention
14 juin 2005
-
mmh ... il existe des algorythme probabiliste pour déterminer efficacement si un nombre est 1er, par exemple fermat ou miller-rabin

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.