Algo

recherche nombre premier

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : recherche nombre premier

crapodesiles

voila un bout de mon code :

Code :

// la partie facile ..
si n<2 alors
retourner faux
fin si
si n == 2
retourner vrai
fin si
si (n modulo 2) == 0
retourner faux
fin si
// la partie compliqué
pour i de 2 jusqu'a I(n/2)I (partie entiere de n/2) // j'hesite avec racine carre de n sqrt(n)
si (n != i) et (n modulo i) ==0
retourner faux
fin si
fin pour
retourner vrai
FIN

votre opinion ?
est ce que dans ma boucle le test de fin peut etre sqrt(n) ??

Message cité 1 fois

Publicité

Trap D

Moi je ferais

Code :

pour i de 3 a I(square(n)) par pas de 2

avec la même signification pour I

matafan

Ouais enfin square_root, parce que square ça veut dire ^2.

elianor

bannie 17 fois

crapodesiles a écrit :

votre opinion ?

trop lourd. A quoi ça sert de tester à la main des choses qui marchent dans le cas général ? (n%2)

crapodesiles a écrit :

est ce que dans ma boucle le test de fin peut etre sqrt(n) ??

oui, mais tu es prié de le prouver mathématiquement d'abord

---------------
JE JE SUIS LIBERTINEEEEEEEEEEE JE SUIS UNE CATINNNNNNNNN §§§§§§§§

tropicano

Ton code à l'air de renvoyer un booléen, il te sert à rechercher des nombres premiers ou à les tester ?.
Car si tu dois juste verifier si un nombre est premier il y a peut-etre pas nécessairement besoin d'une boucle, suffit d'appliquer le théorème de fermat.

Message cité 1 fois

Profil supprimé

tropicano a écrit :

Le petit théorème de Fermat est une condition nécessaire mais non suffisante pour qu'un nombre soit premier.

pains-aux-raisins

Fatal error

Il y a le crible d'Eratostène qui n'est pas très performant.

Récemment, l'algorithme AKS (Agrawal -Kayal -Saxena) permet de déterminer en temps polynomial si un nombre est premier.

Enfin, il y a le test de Rabin-Miller qui lui est probabiliste. On n'est pas sûr à 100% de la primalité. Par contre il est à l'heure actuel l'un des plus rapides.

Message édité par pains-aux-raisins le 04-12-2005 à 20:37:42

FORUM HardWare.fr

Programmation

Algo

recherche nombre premier

Sujets relatifs
recherche Programmeur C++/DirectX/OpenGL - Son Of Destiny - RPG 2D/3D	Recherche du monde pour projet de logiciel cs
Tableau [ ] [ ] --- recherche des indices (x,y)	Compter le nombre de ligne dans un fichier texte sous Windows
[Excel] Compter un nombre de 0 contigues, la suite de 0 la plus longue	recherche webmaster
Recherche d'une interface	nombre max de copie caché lors d'un envoie de mail.
[Résolu] Fonction Execlp avec nombre parametres variable	Recherche de programmeurs pour un jeu php
Plus de sujets relatifs à : recherche nombre premier

Page générée en 0.045 secondes