1 000 000 DE NOMBRES PREMIERS EN 0.062 SECONDES ?

Commentaire de JCDjcd le 16/12/2003 21:22:57

Heu petit probleme ...

"
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

Commentaire de TeLeTUbIz le 16/12/2003 21:54:42

Pardon pour le chrono, j'ai pas mis la bonne version de mon time.h, elle était buguée car elle utilisait des floats, pas assez précis lors de la soustraction qu'il y'avait à faire.
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.

Commentaire de Kirua le 17/12/2003 02:39:07

j'ai pareil, 0,062s, c'est fou, comment ça peut être calculé aussi vite O_o ?

Commentaire de TeLeTUbIz le 17/12/2003 14:39:38

heureux: "Bonjour, il y a moyen de faire un peu plus rapide avec les nombres peudo premiers". Euh ??? Pourrais tu expliquer la méthode ? J'aimerais bien optimiser encore le prog si c'est possible.

Merci d'avance.

Commentaire de TeLeTUbIz le 17/12/2003 14:55:49

JCDjcd: "[snip= erreur"] une autre question : je suis cense visualiser ou tes nombres premiers trouves ??"
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.

Commentaire de TeLeTUbIz le 17/12/2003 15:13:44

Ah mais bien sur !!! J'avais oublié ! D'ailleurs, ymca2003 a fait un programme sur ça, et je l'aime bien car il utilise une classe qui fait toutes les opérations sur les grands entiers: class BigInt

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.

Commentaire de Kirua le 17/12/2003 17:49:59

je sais ce qu'est le crible d'eratosthène, merci qd même lol, quant à s'arrêter à la racine du nombre maximum, c'est juste de la logique ;-) y a tt un dvp attenant.

ceci dit, c'est réellement calculé à une vitesse phénoménale, c'est très bien joué.

Commentaire de TeLeTUbIz le 20/12/2003 20:47:21

ouai, je connais le test des Indiens; enfin, j'en ai entendu parler.
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.

Commentaire de Kirua le 20/12/2003 21:23:26

slt, moi aussi j'ai lu ce numéro hors-série de S&V, et j'ai aussi été voir le document des 3 indiens (en fait, 2 étudiants et un prof si je me souviens bien) sur internet, eh ben c t pas facile du tout O_o j'ai 16 ans donc je suis pas encore un monsieur tout le monde lol, mais ça reste assez complexe. ils parlaient d'un algo de 11 lignes, mais en fait, c'est 11 lignes de "pseudo code", càd écrit en anglais/code du genre

si patata alors tatata

seulement, vérifier patata prends pas mal de lignes lol :-P

Commentaire de TeLeTUbIz le 20/12/2003 21:35:09

J'éssaierais de me procurer ce numéro de science et vie.
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 !

++

Commentaire de Sun-Burst le 31/12/2003 04:54:10

Travail réalisé en 0.047s pour 1 000 000 de nombres scannés :) c'est dingues !!
Mon pc : amd athlon XP 2600+ avec 1024mo de ram

le crible d'Eratostene <-- je m'en souviendrais

Commentaire de coucou747 le 17/07/2004 20:17:20 administrateur CS

Le défaut de ton programme si j'ai bien lu tt les commentaires, c'est simplement que l'on ne peut pas le laisser tourner tt une nuit pour tester tt les nombres et les écrire dans un fichier, car avec un crible, on a ubne taille maximale de tableau, et on ne peut pas la redimantionner (sans perdre bcp de temps) alors la solution est simple, tu fait ça :

#include <stdio.h>
unsigned long int a=2, b, r;
main()
{
while (1==1)
{
a++;
r=1;
for (b=2 ; b*b-1<a ; b++)
{
if ( a%b==0 )
{
r=0;
break;
}
}
if (r==1)
printf("\t%d",a);
}
}

alors évidement, tu perds bcp de temps, au début, mais bon ça fonctionne a l'infinit, pour l'aréter, faites ctrl + C ...
Sinon, le test créé par les trois indiens, c'est très bien, mais c'est un peu compliqué a metre en place, il y a des calculs de log() (math.h) et si vous voulez les utiliser vraiment avec tt la puissance, il faut faire une classe qui permetrais d'utiliser des grands nombres (bigint, j'essai d'en faire une en c)
et avec ça, vous ajoutez aux fonctions de calculs + - * / % ^ les fonctions log ect... (bonne chance, si vous arivez a metre ça en place, les log, c'est du programme de terminale, je rentre en première, et j'ai pas envi de prendre de l'avance).
Je ne comprends pas pourquois tu dis que tu teste jusqu'a la racine du nombre, normalement dans un crible, tu fais :


#include <stdio.h>
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)

Commentaire de garslouche le 22/07/2004 15:09:49

Pour ce qui est de l'algo des indiens on en avait parlé il y a qq temps sur ma source "math.h reprogrammé". Il y a un lien pour le visionner.
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

Commentaire de garslouche le 22/07/2004 21:51:12

cachan

Commentaire de Kirua le 10/01/2005 08:47:39

ératosthène et miller-rabin c'est pas le même usage, ça se compare pas.

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).

Commentaire de Kirua le 10/01/2005 17:48:09

ah d'accord, j'aurais pas pu deviner ^^. l'admin aurait pu en laisser un qd même, c'est butor...

Commentaire de Kirua le 10/01/2005 18:50:52

Ah d'accord, je pensais que c'était un coup de gueul féroce contre les double postes. Ben comme ça on est fixé: les admins aussi sont fébriles et impatients avec le serveur.

Commentaire de TeLeTUbIz le 10/01/2005 22:09:31

Miller Rabin ok, mais il faudrait aussi l'autre test celui de (?). (je ne me souviens plus du nom). Deux tests vallent meux qu'un pour ca.
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 ?

Commentaire de coucou747 le 10/01/2005 22:25:15 administrateur CS

non, justement c'est son interet, il founrnit une réponse sure à 100%...

Le seul défaut c'est qu'il est super long à exécuter et super dur à comprendre (comparé à miller rabin...)...

Commentaire de TeLeTUbIz le 11/01/2005 10:12:25

Hmmm. Ce test m'interresse. Enfin un de ces jours je m'y attarderai.

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.

Commentaire de TeLeTUbIz le 12/06/2010 10:01:45

C'est-à-dire ? Ecrire chaque nombre sur une ligne d'un .txt ?

Commentaire de TeLeTUbIz le 14/06/2010 15:03:59

Il suffit de regarder le source. C'est très facile.

Commentaire de TeLeTUbIz le 14/06/2010 15:16:45

De souvenir, c'est codé sur des uint32 donc la limite c'est évidemment 2^32.
Regarde le main pour voir comment on sort la liste, ensuite suffit d'écrire dans un fichier.