1 000 000 DE NOMBRES PREMIERS EN 0.062 SECONDES ?
Utilisateur anonyme
-
16 déc. 2003 à 15:14
inconnu145 Messages postés 4 Date d'inscription vendredi 11 juin 2010 Statut Membre Dernière intervention 14 juin 2010 - 14 juin 2010 à 15:27
inconnu145 Messages postés 4 Date d'inscription vendredi 11 juin 2010 Statut Membre Dernière intervention 14 juin 2010 - 14 juin 2010 à 15:27
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/18755-1-000-000-de-nombres-premiers-en-0-062-secondes
https://codes-sources.commentcamarche.net/source/18755-1-000-000-de-nombres-premiers-en-0-062-secondes
14 juin 2010 à 15:27
14 juin 2010 à 15:16
Regarde le main pour voir comment on sort la liste, ensuite suffit d'écrire dans un fichier.
14 juin 2010 à 15:10
et le max de nombres a chercher et bien 2^32?
14 juin 2010 à 15:03
12 juin 2010 à 10:03
12 juin 2010 à 10:01
11 juin 2010 à 18:59
11 janv. 2005 à 10:12
PUB: ;-)
** je vais bientôt déposer une source sur le calcul dans le champ fini de Gallois GF(2^8) ainsi que l'algo Rijndael (AES) en cryptage / decryptage dynamique.
11 janv. 2005 à 10:06
PUB: ;-)
** je vais bientôt déposer une source sur le calcul dans le champ fini de Gallois GF(2^8) ainsi que l'algo Rijndael (AES) en cryptage / decryptage dynamique.
10 janv. 2005 à 22:25
Le seul défaut c'est qu'il est super long à exécuter et super dur à comprendre (comparé à miller rabin...)...
10 janv. 2005 à 22:24
coucou, arrête de dire que le crible est inutile, c'est un usage différent, c'est tout. si ça ne TE sert pas, c'est bien ainsi, mais ça te regarde. sans vlr être agressif (faut tjs se méfier ici ^^), tu es trop carré.
10 janv. 2005 à 22:09
Eratostene ne sert pas à faire des grands nombres permiers, on ne peux donc pas dire qu'il est inutile. Il a d'autres utilitées (génération d'une suite premiere; ca sert dans plusieurs domaine, notamment dans la crypto).
J'ai toujours pas vu le test des Indiens. Est-ce un algo probabiliste ?
10 janv. 2005 à 20:12
et je connais l'utilisation des algos miller rabin, eratostène (qui depuis longtemps est inutile...), et celui des indiens (qui pour le moment reste inutile...) J'ai passé assez de nuit blanches à lire et relire des tutos que je connais les principes de crypto RSA et que je sais comment faire (globalement) un générateur de nombre premiers de 128 bits (il ne me reste que le test de miller rabin, ce qui est le plus compliqué, j'en suis concient...)
10 janv. 2005 à 18:50
10 janv. 2005 à 18:40
Veuillez excuser, les journees sont fort longues et je fatigue.
10 janv. 2005 à 17:48
10 janv. 2005 à 10:13
10 janv. 2005 à 08:47
pour ton code coucou, faut pas faire while(1==1) mais while(true), ou while(1), enfin, ce que tu veux, mais c'est pas la peine de lui faire faire un test de plus (j'imagine qd même que le compilo optimise ce genre de trucs).
c'est pas jusque b*b-1 mais juque b*b. sinon pour 4, tu ne testes pas le 2 sauf erreur, et ça déclare 4 premier... j'ai pas fait le test.
tu retestes tous les diviseurs pour chaque nombre, tu ne devrais tester que les nombres premiers... en utilisant ératosthène pour générer les NP jusque -par exemple- 1 milliard, tu peux, avec un algo naïf dans le genre de celui que tu proposais, aller jusque quasiment 10^18 (en fait, jusque le produit des deux derniers nombres premiers).
tu peux aussi zapper tous les pairs, ça ne coûte rien comme code ou presque, et c'est tjs la moitié des nombres (tu traites 2 à part).
9 janv. 2005 à 17:50
Si ça peut répondre à ta question...
22 juil. 2004 à 21:51
22 juil. 2004 à 18:44
22 juil. 2004 à 15:09
Mais vous verrez que le premier test est dejà bien compliqué à programmer. J'en ai parlé à 2 copains de Normal Sup et ils sont restés bloqués une demi heure sans reponse! Autant dire que pour le commun des mortels c'est se ruiner la cervelle
18 juil. 2004 à 10:22
Le réel défaut de mon programme est que j'utilise un crible d'Eratosthene, donc on doit forcément commencer à analyser les nombres depuis 2 jusqu'à un x spécifié.
Donc on doit définir un tableau dès le départ. Si on veux aller plus loin, on à qu'à le redimensionner, mais ca ne prend pas trop trop de temps.
L'algorithme que tu marque est le plus simple: c'est un algo de factorisation très bourrin (pour chaque nombre, tester s'il a des diviseurs en les testants tous).
Il a un indice de complexité énorme et il faudrait plusieurs jours pour trouver tout les premiers jusqu'à 2^32 alors qu'il ne faut que 8 minutes bien pesées avec un crible d'Eratosthene optimisé. Celui là nécessite au grand maximum 256 Mo de mémoire.
En fait, je ne cherche pas à aller plus loin car les entiers sont codés sur 32 bits seulement, donc pour aller plus loin, il faudrait faire des combinaisons complexe avec des tableaux; un truc que j'ai étudié cette année, mais bien trop compliqué.
Sinon, le test des Indiens, au même titre que Miller-Rabbin et compagnie, ce n'est qu'un test qui permet de savoir si un nombre est premier ou pas, mais en aucun cas c'est un algo de génération comme celui d'Eratosthene. C'est pratique pour trouver de très grands nombres premiers, mais pas pour trouver tout les nombres p entre 1 et x.
Enfin, ton algo n'est pas du tout optimisé, mais c'est le principe. J'utilise la racine afin de la stocker dans une variable b par exemple. Ainsi, à chaque boucle il y'aura le test a<b et non a*a < b qui a chaque tour recalculerais le carré de a (c'est rapide, mais suffisamment lent pour ralentir le prog)...
Il m'a fallu plusieurs jours (voir semaines) pour optimiser correctement l'algo.
17 juil. 2004 à 20:17
#include <stdio.h>
unsigned long int a=2, b, r;
main()
{
while (1==1)
{
a++;
r=1;
for (b=2 ; b*b-1
main()
{
int n[1000] ;
int i, x , y ;
x=2;
for (i=0;i<1000;i++)
n[i]=0;
while (x<1000)
{
for (i=x;i*x<1000;i++)
{
*(n+i*x)=1;
}
if (*(n+x)==0)
printf("%d",x);
printf("\t");
x++;
while (n[x]==1){
x++;
}
}
printf("\n");
}
enfin, la j'ai pas du tout optimisé le code, mais t'as qu'un suel test jusqu'a la racine (et t'es pas obligé d'utiliser math.h pour if (a>sqrt(b) tu met if (a*a>b) c'est bcp plus rapide a faire)
1 janv. 2004 à 17:27
31 déc. 2003 à 04:54
Mon pc : amd athlon XP 2600+ avec 1024mo de ram
le crible d'Eratostene <-- je m'en souviendrais
20 déc. 2003 à 21:51
sinon, ben ds le S&V ils expliquent pas pq ça marche. J'aimerais bien retrouver ce numéro
20 déc. 2003 à 21:35
J'espère qu'ils expliquent aussi pourquoi ça fonctionne.
oi j'ai entendu comme Kirua, càd que l'algo est simple, mais utilise des probs assez complexe à résoudre. C'est un peu comme pour les algo sur la photo. Comme c'ets visuel, c'est très simple pour un homme, mais pour un ordi qui est très linéaire, c'est hachement cho !
++
20 déc. 2003 à 21:30
d'habitude les algorithme de recherche des nombres premiers sont en n carre, ou en en autre chose, mais pas polynomial
20 déc. 2003 à 21:23
si patata alors tatata
seulement, vérifier patata prends pas mal de lignes lol :-P
20 déc. 2003 à 21:11
salut
20 déc. 2003 à 20:47
Mais il paraît que l'algo est assez complexe. Sinon, le test de Miller fonctionne pas mal.
Mais un algo rapide serait sympa, par exemple pour générer des grosses clés RSA. Dommage que ce soit interdit pour le civil.
20 déc. 2003 à 20:34
Le crible d'erathostene c'est bien...mais j'ai entendu parler d'un nouveau test de primalité découvert par trois etudiants indiens j'ai imprimer des feuille qui en parlait mais j'ai pas eu le temps de les lire. Il est bien expliquer dans science et vie mais je sais plus qu'elle numéro faut aller sur le site.
cette algo permet de verifier si un grand nombre est premier tres rapidement mais pas pour avoir tout les premiers jusq'un certain nombre.
@+
17 déc. 2003 à 17:49
ceci dit, c'est réellement calculé à une vitesse phénoménale, c'est très bien joué.
17 déc. 2003 à 15:16
17 déc. 2003 à 15:13
D'ailleurs, il fait deux test, celui de Miller et un autre, et on fait autant d'itérations qu'on veux.
Mais ici, Miller, c'est aps possible: d'un, c'est très lent; et l'intérêt n'est pas le même: moi je veux pleins de nombres premiers; Millers donne un très grand. Miller, c'est plus pour le cryptage RSA.
17 déc. 2003 à 14:56
Donc voila une etrange utilisation d'un Random ...
17 déc. 2003 à 14:55
Pour l'erreur, je la connais. Evite de mettre un nombre en dessous de 100, car pour cinq par exemple, il fait zéro appel et ça le bloque (j'ai pas encore étudié le prob).
Essaie 1 000 000 par exemple, même sur un vieux PC ca tournera vite, puis ca prendra que 62 Ko de mem.
Une fois que tu auras fait un crible, ca te demandera si tu veux sauvegarder. Appuie sur n (non), ca n'a pas d'utilité; sauf si il y'a 3-4 minutes de calcul (genre, si t'as mis 1 milliard). Alors, il va te demander si tu veux voir les résultats; dis oui (o). Ensuite, pour le rang de départ mets 1 (entrer) et pour l'arrivé mets 1 000 000 (de toute façon il s'arretera quand il n'y en aura plus).
Bonne chance.
P.S: désolé pour les quelques bugs du main et la dégulasseurie de la présentation, j'ai tapé ça à l'arrache pour montrer la possibilité de la classe.
17 déc. 2003 à 14:48
Crible d'Eratosthene est la solution mon ami !
Tu fais un tableau de 2 à n. Ensuite, comme 2 n'est pas barré, tu rayes tout ces multiples (2,4,6,8...). Ensuite tu avances de un: 3 n'ets pas barré, donc il est premier: tu rayes tout ses multiples: 6,9,12...
ensuite 4: il est rayé donc pas premier, ensuite 5, etc... Ca reviens à la définition d'un nombre premier: c'ets le premier nombre de toute une gamme de multiples. C'est très simple (niveau CE2 lol) et rapide.
Mais pour aller encore plus vite et bouffer moins de mémoire, il y'a trois choses à faire:
le tableau commence à 3 et va de deux en deux (que les impairs). Ainsi, le nombre à l'indice i dans le tableau est 2*i+3. Ensuite, un indice correspond ici à un seul bit; on recueille donc pour chaque nombre étudié une valeur booléenne: rayé, ou pas.
Enfin, les règles habituelles: on peut pas (par calcul) trouver un nombre premier après la racine du maximum du tableau; on commence à rayer à partir du carré du nombre et par pas de 2* le nombre...
Voilu.
P.S: en fait, ce programme m'a surtout servit à apprendre à utiliser un tableau où les cases font un nombre n de bits (plutôt qu'un multiple de 8). Ca économise la mémoire.
17 déc. 2003 à 14:39
Merci d'avance.
17 déc. 2003 à 14:27
*************************************
Bienvenue dans EratOx !
Charger un fichier ? o/n
Precisez un nombre maximum a scaner: 5
*************************************
et ensuite :
*************************************
NBP2 a causé une défaillance de page dans
le module NBP2.0B.EXE à 019f:00401660.
Registres :
EAX=00770e10 CS=019f EIP=00401660 EFLGS=00010246
EBX=00000000 SS=01a7 ESP=0064fcfc EBP=0064fd10
ECX=00000080 DS=01a7 ESI=81bb0a4c FS=6e57
EDX=000071f0 ES=01a7 EDI=00000000 GS=0000
Octets à CS : EIP :
8a 1c 10 23 cb 85 c9 74 04 b0 01 eb 02 32 c0 5b
État de la pile :
00540000 0064fdcc 00210080 00000000 000071f0 0064fd3c 0040123d 00038f80 00000005 00000000 0064fdcc 5ae79eff 00071f01 5ae79eff 00038f80 7fffffff
*************************************
une autre question : je suis cense visualiser ou tes nombres premiers trouves ??
17 déc. 2003 à 02:39
17 déc. 2003 à 00:11
Bon courage
16 déc. 2003 à 21:54
C'est corrigé.
De plus, pour voir les nombres calculés, il faut lorsque le programme demande voulez vous voir les résultats taper sur la touche 'o' et indiquer par exemple de 1 à 100 pour les rangs. S'il y'en a moins, cela s'arretera.
Enfin, pour répondre à ta question sur les 1 millions, il y'a en réalité pour 1 million de nombres bien moins de 1 millions d'itérations. Par contre, plus le nombre max est grand, plus il y'aura d'itérations, allant même jusqu'à dépassé le nombre max.
Par exemple, pour le nombre 100, 3 itérations suffisent ! (une pour le nombre 3, une pour le nombre 5, une pour le nombre 7; après on dépasse la racine, tout les nombres premiers inférieurs à 100 on été trouvés). Bien sûr, chaque itérations se décompose en d'autres itérations, mais c'est très rapide.
Pour info, 1 000 000 d'itérations avec ta boucle sont faites sur mon PC dans un temps trop court pour être affiché (il me marque 0)
Réssaie mon prog qui marche mieux mnt, et merci pour les bugs.
16 déc. 2003 à 21:29
je suis cense les visuliser ou ??
De plus cela me parait impossible de faire 1 million en moins d'une seconde ... essaye de faire :
int i;
for(i=0;i<1000000;i++);
si ca fait plus que 0.062 secondes il y a un probleme ....
16 déc. 2003 à 21:22
"
Bienvenue dans EratOx !
Charger un fichier ? o/n
Precisez un nombre maximum a scaner: 100
travail realise en -22.13s
Voulez vous enregistrer ce travail dans un fichier de sauvegarde ? o/n
"
c'est normale que ce soit <0
16 déc. 2003 à 15:14
pour optimiser le crible, la table de nombres ne contient que les nombres impairs à partir de trois (car tout les autres paires ne sont pas premiers) puis chaque nombre est codés sur un seul Bit.
Donc, pour tout les __int32 non signés il faut seulement 256 Mo de mémoire. Ou alors 62 Ko pour 1 000 000 de nombres.
De plus, on s'arrète de 'rayer le nombres' après la racine du max.
Si vous comprenez rien à tout ça, ou si le code vous semble illisible, vous pouvez écrire un message, je tenterais de m'éclaircir.