Attention ! : ce programme est déconseillé aux programmeurs cardiaques, souffrant d'epilepsie ou trop integres et soucieux de produire un bon code!

Oui alors je met le code, mais vous devez savoir que :
- je suis en 1ere S, donc les maths je fais encore des trucs tout petits
- Je suis pas bon en prog (mais ca vous le savez déjà logiquement)
- Je n'ai pas cherché a optimiser complement ce prog, et je sais que pour des nombres un tantinet gros ca tourne longtemps avant de trouver. en fait j'ai quand même fait ca, car je prefere avoir fait mon propre programme avec mes seules connaissances qu'avec idées d'autres meilleurs que moi et dont je ne comprendrai peut etre rien. Donc oui, c'est un programme a la con, mais bon...

Alors, l'idee c'est qu'en se lancant, le programme demande a l'utilisateur combien des premiers nombres premiers (2,3,etc... : je les appelle ici diviseurs premiers) il veut utiliser pour calculer, et il les stocke (après les avoirs calculé) dans un tableau de int de la taille voulue.
Plus il y aura de diviseurs premiers, plus la memoire sera chargée mais aussi plus ca ira vite.

Jusque la, ca va, ca fonctionne. Ensuite l'utilisateur est invité a donner le nombre de départ ainsi que le nombre final. L'ordi va donc chercher les nombres premiers entre ces deux nombres.
Ca marche toujours jusque là.

Ensuite, le prog utilise une boucle for qui fait tourner tout les nombres a tester. Pour chaque nombre elle appelle la fonction que j'ai appelé noyau, qui est réellement le coeur du programme, c'est elle qui teste le nombre. Pour cela, elle utilise le tableau de diviseurs premiers, en comparant chaque diviseurs premier avec le nombre. Si l'un d'entre eux est égal au nombre a tester, ce dernier est immédiatement reconnu premier (noyau() se termine et renvoie la valeur 1, signifiant qu'il l'est). Si le modulo du nombre a tester pas l'un des diviseurs prems est nul, c'est l'inverse, la fonction se stoppe en disant "pas premier!". Si tout les modulo sont different de 0, la fonction teste ensuite tout les nombres entre le dernier diviseur premier et la moitié du nombre a tester, quittant si un modulo est nul. Si a la fin aucun modulo n'est nul, elle renvoie 1.

Le voila (note : vraiment désolé pour la mise en forme, mais ca marche pas...) :

Citation : code

int noyau (long int nbr , long int nbrtrouves, int premsdiv[]){

/* nbr = le nombre a tester - nbrtrouves = le nombre de diviseurs premiers - premsdiv[] = le tableau des diviseurs premier */

long int k; /* Pour la 2e boucle for */
int u; /*variable qui sert a se balader dans le tableau des diviseurs premiers */
int premier = 1; /* si =1, c'est premier, si =0 c'est pas */

if((nbr==0)||(nbr==1)){ /* Au cas où le nombre soit egal a 0 ou 1 */
return 0;
}else{
for(u = 0 ; u < nbrtrouves ; u++){ /* Comparaison ac tab des diviseurs prems */
if ( nbr == premsdiv [u]){ /* si le nbr = un des diviseurs premiers */
return 1;
}else if ((nbr % premsdiv[u])==0){ /* si c'est divisible entierement, on sort*/
premier = 0;
return 0;
}
}
if ( nbr <= premsdiv [nbrtrouves])
/* si le nombre se trouvait entre les diviseurs premiers et qu'on est pas sorti, c'est qu'il est premier */
{
return 1;
}

for(k=premsdiv[nbrtrouves] ; k <= ((nbr/2)+1) ; k++){ /* maitenant on teste tout les diviseurs entre le dernier diviseur premier et la moitié du nombre (+1 pour etre sur) */
if((nbr%k)==0){
premier = 0;
break; /* On sort dès qu'on a trouvé un diviseur */
}
}
}
return premier ; /* Le retour de la fonction est si c'est premier ou non */
} /* Fin de la fonction */

Voila. Je vous avait prevenu, c'est pas joli-joli. Mais bon.
Normalement vous n'avez pas besoin du reste du code, c'est de la forme.
Voilou

Toineo, qui sent qu'il va se faire taper sur les doigts

Citation : Toineo

Le voila (note : vraiment désolé pour la mise en forme, mais ca marche pas...) :

Ça commence mal.


Et au lieu de tout le blabla, commente SOBREMENT ton code.

Citation : Toineo

Toineo, qui sent qu'il va se faire taper sur les doigts

Mias tu sais que tu as de l'intuition toi !


Pour soulager les yeux des lecteurs de ce forum, voici le code placé dans les balises convenables (cliquer sur la liste déroulante et chercher la ligne portant la mention "C", si tu ne sais pas faire ça, on n'est pas sorti de l'auberge).



Personnellement, je ne vais pas rentrer dans ton code tant que tu ne donneras pas un programme COMPLET compilable (et sortie visible avec des printf) ce qui suppose que tu places une fonction main dans ton code.

Citation : candide

Ça commence mal.

Citation : candide

Pour soulager les yeux des lecteurs de ce forum, voici le code placé dans les balises convenables (cliquer sur la liste déroulante et chercher la ligne portant la mention "C", si tu ne sais pas faire ça, on n'est pas sorti de l'auberge).

Bon quand même je suis pas un boulet a ce point. C'est ce que j' ai fait, j'ai essayé plusieurs fois mais ca ne marchait pas.

Et puis sinon pour le code, la seule partie qui nous interesse est là, le reste disais-je n'est que de la mise en forme. C'est la variable nbr que je voudrais "agrandir". Sinon je sais ce qu'est un code complet compilable, pas la peine de me prendre pour un débile non plus. Mais vraiment, le reste ne fait que creer le tableau, envoyer les nombres a cette fonction et les afficher.

Et si tu veux absolument le code complet, il va falloir attendre, je n'ai plus le temps là.

Toineo

Citation : Toineo

Et si tu veux absolument le code complet, il va falloir attendre, je n'ai plus le temps là.

Ça tombe bien moi non plus.

Citation : Toineo

Bon quand même je suis pas un boulet a ce point. C'est ce que j' ai fait, j'ai essayé plusieurs fois mais ca ne marchait pas.

Si tu avais lu le mode d'emploi, tu aurais vu que les balises codes ne sont pas rendu dans l'aperçu en temps réel et qu'il faut appuyer sur "Aperçu final" pour les voir.

Citation : Toineo

Et puis sinon pour le code, la seule partie qui nous interesse est là, le reste disais-je n'est que de la mise en forme. C'est la variable nbr que je voudrais "agrandir". Sinon je sais ce qu'est un code complet compilable, pas la peine de me prendre pour un débile non plus. Mais vraiment, le reste ne fait que creer le tableau, envoyer les nombres a cette fonction et les afficher.

Et si tu veux absolument le code complet, il va falloir attendre, je n'ai plus le temps là.

Toineo

Le but n'est pas d'avoir un code complet, au contraire. Le but c'est d'avoir un code compilable. Or, pour l'instant, nous n'avons que la fonction. Il faut donc, nous même, compléter le code.
Le but est que tu nous donne un code minimal ET compilable.

Bonne continuation.

Citation : Mikechaos

Si tu avais lu le mode d'emploi, tu aurais vu que les balises codes ne sont pas rendu dans l'aperçu en temps réel et qu'il faut appuyer sur "Aperçu final" pour les voir.

Pourtant il m'a semblé que j'ai essayé l'apercu final, et que ca n'a pas marché...
Enfin bref

Citation : Mikechaos

Le but n'est pas d'avoir un code complet, au contraire. Le but c'est d'avoir un code compilable. Or, pour l'instant, nous n'avons que la fonction. Il faut donc, nous même, compléter le code.
Le but est que tu nous donne un code minimal ET compilable.

Bonne continuation.

Oui, mais en fait l'histoire c'est que si je veux un code compilable, il faut que je mette tout, sauf si je le compacte pour qu'il ne teste plus qu'un seul nombre. Je fais comme ca? (ca sera beaucoup plus simple ...)

Toineo

EDIT : voici le code allégé. Dans ce cas, le tableau de diviseurs premiers ne sert pas vraiment beaucoup mais bon...
Attention il n'est pas forcement très optimisé. Et j'ai fait exprès de prendre les même nom pour les variables "normales" comme pour celle qui servent au prototype de la fonction.

L'indentation n'a jamais fais de mal à personne.
Il faut un petit int devant main.

Est totalement inutile.
Le resultat de mon compilo :

Euh tu a raison pour le if.J'y avais pas pensé.

Sinon pour le int devant main je le metterai, mais je croyais que c'était surtout pour le C++
conio.h : tu peux l'enlever, c'est juste que je le mets par défaut dans mes codes.

Pour les autres erreurs j'avoue que je comprends pas. Moi je suis sous code::blocks et ca marche très bien. Si tu sais pourquoi ca fait ca, merci de le communiquer.

Je corrige le code ce soir.

Toineo

Citation : Toineo

voici le code allégé

Allégé ! qu'est-ce que ça aurait été s'il ne l'avait pas été !

Bon, il faut TOUT reprendre :

• Présentation du code (dans codeblocks, il y a un identeur automatique), commentaires non pertinents
• Redéfinition de l'objectif du programme : on ne comprend pas ce qu'il fait aussi bien lorsqu'on l'exécute que lorsque l'on regarde le code-source. Fais SIMPLE : juste un programme qui dit OUI ou NON un nombre donné dans le source (ce qui évite des scanf artificiels) s'il est premier ou pas. Fondamentalement, ton tableau de nombres premiers ne sert à rien.
• Algorithme très confus et compliqué alors que tester si un entier est premier est une question SIMPLE.
• Optimisations sans intérêt.
• Obtention du résultat pour un nombre de l'ordre de quelques milliards (petit nombre) nécessitant une durée relativement longue.
• Plusieurs erreurs ou maladresses : déclaration de main, une fonction est codée et il y a du code dans main (faudrait alors deux fonctions), en-têtes inutiles et non stantard, déclarations de variables un peu n'importe où, appel récursif douteux de la fonction main à la ligne 53, etc.
• Maths à revoir (confusion entre moitié et racine carrée).
  

Un conseil : faire SIMPLE tant qu'on n'a pas besoin de faire autrement.

À mon avis, tu aurais intérêt à te pencher sur le code traitant de cette question sur le forum, ici

Oula ! hey mollo !

Bon, pour te repondre dans l'ordre :
-Bon la presentation d'accord c'est pas génial

-Pour mettre le nombre direct dans le code source, non : déjà j'ai vraiment pas envie de modifier le code et recompiler pour tester chaque nombre. Et c'est aussi pour des amis, qui ne programment pas et donc qui ne peuvent pas modifier le nombre s'il est direct dans le code source. Et franchement, je vois pas ce que ca change de demander a l'utilisateur ce qu'il veut tester.

-pour l'algo et le tableau de premiers, c'est normal parce qu'en fait normalement je teste plusieurs nombres (dans un intervalle donc). Donc ici le tableau ne sert pas vraiment, je suis d'accord. Mais par contre quand on a un intervalle, j'ai testé avec et sans tableau en même temps et le prog avec tableau va plus vite.

-Ce prog est lent, je le sais et comme je l'ai dis plus haut, je ne peut pas faire mieux vu mes connaissances en math.

- Ligne 53 je rapelle main car l'entrée clavier n'est pas correcte.Je suis d'accord qu'il y a surement mieux.

- Par contre je vois pas ou tu vois du code de noyau() dans main(). Où est-ce?

- Pour les en-tete je les mets dans mon code par défaut, ce qui explique leur presence. Parfois ils me servent, d'autres non (comme ici).

- Les variables j'essaye de les déclarer le plus possible juste après les en-tete. Simplement, le tableau de diviseur je suis obligé de le definir uniquement quand je connais sa taille ( la variable nbrdiv, donc dans main. Ca me plait pas non plus.

- Pour la racine carré / la moitié on m'a expliqué aujourd'hui. Je corrigerai donc cela.

Sinon, l'objectif du programme : l'utilisateur veux savoir si tel nombre est premier. Il entre donc ce nombre ainsi que le nombre de diviseurs premiers qu'il veut utiliser (pas vraiment utile pour un seul nombre, sauf si très grand en utilisant beaucoup de diviseurs, mais je repete que ca vient d'un programme qui teste un intervalle de nombre !). Le programme lui repond si le nombre est premier ou non.

Pour le "allégé" : c'est parce que ce prog ne teste qu'un seul nombre, alors que le "non allégé" teste un intervalle de nombre. Je dis allégé car l'autre a du code en plus pas vraiment utile.

Merci pour le code, je vais l'étudier.

Voila
Toineo

Citation : Toineo

-Ce prog est lent, je le sais et comme je l'ai dis plus haut, je ne peut pas faire mieux vu mes connaissances en math.
- Pour la racine carré / la moitié on m'a expliqué aujourd'hui. Je corrigerai donc cela.

Le 2ème point répond au premier

Citation : Toineo

- Ligne 53 je rapelle main car l'entrée clavier n'est pas correcte.Je suis d'accord qu'il y a surement mieux.

Ca ressemble trop à un goto. Tu ne pourrais pas le faire avec une boucle?

Citation : Toineo

- Les variables j'essaye de les déclarer le plus possible juste après les en-tete. Simplement, le tableau de diviseur je suis obligé de le definir uniquement quand je connais sa taille ( la variable nbrdiv, donc dans main. Ca me plait pas non plus.

Il faut passer par l'allocation dynamique avec les pointeurs chose que tu ne connais peut-être pas encore.
Dans ce cas-là tu mets une borne maximum et c'est réglé.

Citation : Pole

Le 2ème point répond au premier

Pas de prob, ca sera corrigé.

Citation : Pole

Ca ressemble trop à un goto. Tu ne pourrais pas le faire avec une boucle?

Si, bonne idée. Je le corrigerai aussi.

Citation : Pole

Il faut passer par l'allocation dynamique avec les pointeurs chose que tu ne connais peut-être pas encore.
Dans ce cas-là tu mets une borne maximum et c'est réglé.

L'allocation dynamique je suis en train de l'apprendre. Dans ce cas on utilise realloc(), ou alors j'ai tout faux?


@candide :
Je suis en train de lire le topic dont tu as mis le lien, mais une chose me parrait notable :
en fait les progs que vous proposez sont faits pour des nombres pas trop gros. Alors, certes mon code est très améliorable, mais par contre moi ce que je veux c'est tester des très gros nombres (d'où mon probleme de variable) et aussi des intervalles de très grands nombres. Et c'est l'utilisateur qui choisit quel nombre tester.
Cela n'empêche, je vais essayer de clarifier et d'optimiser mon code.

Non on doit utiliser malloc.
Très gros nombres : jusqu'à combieu ?
Au dessus de 10^18 ça risque d'être compliqué.

Citation : Toineo

Bon, pour te repondre dans l'ordre :

Tu perds ton temps à me répondre point par point, c'est pas ça qui va améliorer ton code.

Citation : Toineo

-Pour mettre le nombre direct dans le code source, non : déjà j'ai vraiment pas envie de modifier le code et recompiler pour tester chaque nombre. Et c'est aussi pour des amis, qui ne programment pas et donc qui ne peuvent pas modifier le nombre s'il est direct dans le code source. Et franchement, je vois pas ce que ca change de demander a l'utilisateur ce qu'il veut tester.

Tu fais ce que tu veux, si tu veux te disperser, c'est ton droit. Tes petits copains, ils trouveront des applets java de factorisation infiniment plus fiables, rapides et puissants sur le Net.

Citation : Toineo

-Ce prog est lent, je le sais et comme je l'ai dis plus haut, je ne peut pas faire mieux vu mes connaissances en math.

Questions connaissances en maths, ça doit pas dépasser le niveau de la troisième, et encore. T'es en première, non ?

Citation : Toineo

- Ligne 53 je rapelle main car l'entrée clavier n'est pas correcte.Je suis d'accord qu'il y a surement mieux.

En réalité, main peut être appelée récursivement.

Citation : Toineo

- Par contre je vois pas ou tu vois du code de noyau() dans main(). Où est-ce?

Ce n'est pas ce que j'ai dit et je me suis sans doute mal fait comprendre. Tout ce qui est entre les lignes 60 et 100 de ton code devrait être placé dans une autre fonction. Tu l'as bien fait pour le code de ta fonction noyau, il n'y a pas de raison de ne pas le faire pour la portion de code que je viens de signaler. Sans compter que cette portion de code et celui de la fonction noyau font à peu près les mêmes choses (ça s'appelle de la duplication de code, ce qu'on essaye d'éviter, les fonctions sont là pour ça.)

Citation : Toineo

- Pour les en-tete je les mets dans mon code par défaut, ce qui explique leur presence. Parfois ils me servent, d'autres non (comme ici).

Mauvaise pratique car quand on les voit ces en-têtes on attend à ce qu'elles soient utilisées et c'est donc trompeur. En plus, savoir discerner ce dont on a besoin et celles qui ne sont pas utiles fait partie de l'apprentissage (basique) du langage C.

Citation : Toineo

- Les variables j'essaye de les déclarer le plus possible juste après les en-tete.

Non, je ne te parlais pas de tes variables globales déclarées aux lignes 8 et 9 car elles ne me gênent pas plus que ça pour l'instant (alors que l'utilité est loin d'être justifiée mais ce n'est pas une urgence dans ton cas que de régler cette question des variables globales).

Non, je parlais des variables déclarées aux lignes 57, 58, 84. Ce n'est pas interdit mais c'est propre au C99; De toutes façons, tu utilises beaucoup trop de variables pour ce que tu veux faire.

Mais , ce sont là des questions de langage C. Le plus gênant dans ton code, c'est le fait que ton programme ne sait pas ce qu'il fait et que ton "algorithme" est outrageusement compliqué.

Problème SIMPLE, algorithme SIMPLE, codage (souvent moins) SIMPLE !


Je t'invite à nouveau à examiner en détail le code qui est dans le lien que je t'ai donné à la fin de mon dernier post, ça te sera très instructif.

Citation : Toineo

@candide :
Je suis en train de lire le topic dont tu as mis le lien, mais une chose me parrait notable :
en fait les progs que vous proposez sont faits pour des nombres pas trop gros. Alors, certes mon code est très améliorable, mais par contre moi ce que je veux c'est tester des très gros nombres

Arrête de penser à ça. Commence déjà par écrire du code correct, propre et sobre pour un problème FACILE. Ensuite (ou dès maintenant), améliore un petit peu le code en utilisant des entiers "plus grands" de type unsigned long long int (environ 18 chiffres décimaux) et tu verras que l'algorithme naïf rame déjà pas mal (et donc il ramera encore plus avec des nombres plus grands encore).

Vu comment tu as traité ce problème des nombres premiers, tu vas va avoir ENORMEMENT de mal (pour l'instant) à l'adapter pour de très grands nombres (en restant "naïf", tu vas devoir implémenter une division entre grands nombres et je te sens pas du tout le faire pour l'instant).

Citation : Toineo

Et c'est l'utilisateur qui choisit quel nombre tester.

Mirage de convivialité.

Citation : Pole

Non on doit utiliser malloc.

Bon, j'ai tout faux ...
Mais donc si on utilise malloc, on definit toujours le tableau (du moins, dans ce cas, le pointeur vers un tableau) dans main ?

Pour la taille, 10^18 serait déjà très bien. Après, s'il on peut encore augmenter sans alterer l'exactitude, c'est encore mieux. Mais c'est sur, ca mettra du temps (pour tester ces nombres).

A propos du tableau :
Ce tableau de diviseur sert uniquement pour les très gros nombres. Je suis d'accord qu'il :
- est completement inutile pour des nombres pas trop gros, environ jusqu'au milliard
- complexifie considérablement le code. En effet, sans lui, sa définition, son application, j'aurai presque un code "normal" de programme (simple) sur les nombres premiers

Mais lorsqu'on teste un intervalle commencant au minimum a 10^9, là il commence a être utile. Et si je peux faire des nombres encore plus grand, il devrait être encore plus utile.

Citation : Candide

Questions connaissances en maths, ça doit pas dépasser le niveau de la troisième, et encore. T'es en première, non ?

Et alors en premiere j'ai rien appris qui me serve ici. C'est pas de ma faute si on va pas vite.

Citation : Candide

Ce n'est pas ce que j'ai dit et je me suis sans doute mal fait comprendre. Tout ce qui est entre les lignes 60 et 100 de ton code devrait être placé dans une autre fonction. Tu l'as bien fait pour le code de ta fonction noyau, il n'y a pas de raison de ne pas le faire pour la portion de code que je viens de signaler. Sans compter que cette portion de code et celui de la fonction noyau font à peu près les mêmes choses (ça s'appelle de la duplication de code, ce qu'on essaye d'éviter, les fonctions sont là pour ça.)

Je metterai ca dans une autre fonction, donc.

Citation : Candide

Mauvaise pratique car quand on les voit ces en-têtes on attend à ce qu'elles soient utilisées et c'est donc trompeur. En plus, savoir discerner ce dont on a besoin et celles qui ne sont pas utiles fait partie de l'apprentissage (basique) du langage C.

Je sais discerner, c'est juste que je les mets comme ca j'ai pas a m'en preocupper. Oui, c'est de la flemme. Mais c'est vrai que comme je poste ce code, je dois enlever les inutiles.

Pour la fin sur la complexité : j'ai déjà fait un prog dans le même style que ceux dans le post (les "super naifs", avec un code propre : oui ca ca va c'est quand même pas trop dur pour moi). Ici, ce prog est une amélioration (certes plus complexe) qui devrait permettre d'accelerer le mouvement sur les gros nombres. Parce que les programmes tout simple vont ramer a mort sur des gros nombres, alors si je peux accelerer ca d'un chouya je serait content (même si je me doute que ca sera quand même très long)

Et pour le scanf : moi j'appelle pas ca un "mirage de convivialité" mais un code plus pratique pour les gens qui ne programment pas.

Citation : Candide

Tu fais ce que tu veux, si tu veux te disperser, c'est ton droit. Tes petits copains, ils trouveront des applets java de factorisation infiniment plus fiables, rapides et puissants sur le Net.

C'est pas de la dispertion. Et puis t'es pas obligé de te moquer (pour rester poli) de mes amis et moi

Et puis derniere chose : si tu tiens absolument à :
- toujours avoir le dernier mot et me faire avoir tort (p.e sur l'histoire du scanf)
- Bien montrer que je suis nul
- me critiquer le plus possible
C'est pas vraiment la peine de répondre. Je sais pas pourquoi, soit tu peux pas me blairer, soit tu trouve que je suis un débile sorti du fin fond des ages, soit je ne sais quoi encore, mais je te trouve vraiment pas sympa et parfois limite humiliant.
Honnetement, je prefere parler avec des gens qui pensent ce qu'ils pensent mais qui restent aimable et pédagogiques.
Après, a toi de voir

Citation : Toineo

Pour la taille, 10^18 serait déjà très bien.

Avec des unsigned long long tu n'en sera pas loin.

Citation : Toineo

Mais lorsqu'on teste un intervalle commencant au minimum a 10^9, là il commence a être utile.

Bof

Citation : Toineo

Citation : Candide

Questions connaissances en maths, ça doit pas dépasser le niveau de la troisième, et encore. T'es en première, non ?

Et alors en premiere j'ai rien appris qui me serve ici. C'est pas de ma faute si on va pas vite.

La racine carrée, c'est en quelle classe ?

Citation : Toineo

Ici, ce prog est une amélioration (certes plus complexe) qui devrait permettre d'accelerer le mouvement sur les gros nombres.

Grâce à ton tableau ? C'est très discutable. Admettons que tu veuilles savoir si un entier de l'ordre de <math>\(2%5E%7B64%7D\)</math> est premier ou pas. Tu vas avoir besoin des nombres premiers inférieurs à <math>\(2%5E%7B32%7D\)</math> et on peut en connaître le nombre de tels nombres premiers, je dirais de l'ordre de <math>\(2%5E%7B26%7D\)</math>. À raison de 4 octets par entier, on arrive à <math>\(2%5E%7B28%7D\)</math> octets, pas loin de un Go de mémoire. Ça me parait bien cher. C'est de la petite optimisation, tu irais BEAUCOUP plus vite si tu t'arrêtais avant la partie entière de la racine carrée, et tu élimines BEAUCOUP de cas inutiles simplement en retirant les multiples de 2, 3, 5, et 7 dans les tests.

Citation : Toineo

alors si je peux accelerer ca d'un chouya je serait content (même si je me doute que ca sera quand même très long)

Tu ne fais pas les bonnes optimisations. Faut un peu réfléchir avant de se lancer dans le codage en dur.

Citation : Toineo

Citation : Candide

Tu fais ce que tu veux, si tu veux te disperser, c'est ton droit. Tes petits copains, ils trouveront des applets java de factorisation infiniment plus fiables, rapides et puissants sur le Net.

Et puis t'es pas obligé de te moquer (pour rester poli) de mes amis et moi

Je me moque pas de tes amis, je dis qu'ils auront un résultat plus fiable, plus avancé, plus rapide en allant ici (troisième lien trouvé dans Google) qui factorise en clin d'oeil un entier de 100 chiffres décimaux (d'après l'essai que je viens de faire).

Citation : Toineo

Et puis derniere chose : si tu tiens absolument à :
- toujours avoir le dernier mot et me faire avoir tort (p.e sur l'histoire du scanf)

Mon but n'est pas de te démontrer que tu as tort mis de te faire gagner du temps pour aller à l'essentiel (les entrées/sorties c'est difficile en C, ça prend du temps, c'est source d'erreurs et n'apporte RIEN à l'écriture des algorithmes ou si peu).

Citation : Toineo

C'est pas vraiment la peine de répondre. Je sais pas pourquoi, soit tu peux pas me blairer, soit tu trouve que je suis un débile sorti du fin fond des ages, soit je ne sais quoi encore,

t'as un problème ou quoi ?

Citation : Toineo

mais je te trouve vraiment pas sympa et parfois limite humiliant.
Honnetement, je prefere parler avec des gens qui pensent ce qu'ils pensent mais qui restent aimable et pédagogiques.
Après, a toi de voir

Non, je t'ai donné des conseils pour ne pas te disperser et progresser étape par étape. Libre à toi de ne pas les écouter. Après tout, je ne veux pas t'empêcher de rêver.

Citation : Candide

Avec des unsigned long long tu n'en sera pas loin.

Oui, justement.

Citation : Candide

La racine carrée, c'est en quelle classe ?

Evidemment qu'on a déjà vu la racine carrée, mais son application sur les nombres premiers on l'a jamais vu. Mais ca y est j'ai compris.

Citation : candide

tu irais BEAUCOUP plus vite si tu t'arrêtais avant la partie entière de la racine carrée, et tu élimines BEAUCOUP de cas inutiles simplement en retirant les multiples de 2, 3, 5, et 7 dans les tests.

Ben faut voir, tu vois ca comment :
-la boucle les sautes (deja les multiples de deux en ne faisant pas ++ mais +=2 pour l'incrementation)?
-On applique les regles de divisibilité qu'on connait, du genre si le nombre ce finit par un nombre pair pour 2, un 0 ou un 5 pour 5, etc... Reste a savoir si c'est plus rapide que de diviser par le nombre lui même ( 2 , 3 , 5...). Car la fonction dès qu'elle trouve un diviseur renvoie immédiatement 0 et se stoppe. Je pourrait pas dire, a vous de voir.

Citation : candide

Tu ne fais pas les bonnes optimisations. Faut un peu réfléchir avant de se lancer dans le codage en dur.

Lidéee c'était d'optimiser un petit peu. Et après j'optimiserai plus, quand j'en saurai plus...

Citation : candide

Je me moque pas de tes amis, je dis qu'ils auront un résultat plus fiable, plus avancé, plus rapide en allant ici (troisième lien trouvé dans Google) qui factorise en clin d'oeil un entier de 100 chiffres décimaux (d'après l'essai que je viens de faire).

Evidemment, mais bon ils n'ont pas besoin de ces nombres non plus...

Citation : candide

Mon but n'est pas de te démontrer que tu as tort mis de te faire gagner du temps pour aller à l'essentiel (les entrées/sorties c'est difficile en C, ça prend du temps, c'est source d'erreurs et n'apporte RIEN à l'écriture des algorithmes ou si peu).

Oui mais on peut travailler sur l'algorithme en laissant ca...

Citation : candide

t'as un problème ou quoi ?

Non, c'est juste que y avait des moments, tu repondais comme si tu était exaspéré. C'est pas super agréable de se faire en.ueuler a chaque fois quoi...
Mais là par exemple (le dernier message quoi), c'était bien (car constructif !)

Citation : candide

Non, je t'ai donné des conseils pour ne pas te disperser et progresser étape par étape. Libre à toi de ne pas les écouter. Après tout, je ne veux pas t'empêcher de rêver.

Non, je dis juste qu'il y a maniere et maniere de donner des conseils.
Et puis t'inquiete pas, je sais très bien que je reste a un stade basique de la programmation.

Toineo

Citation : Toineo

Citation : candide

tu irais BEAUCOUP plus vite si tu t'arrêtais avant la partie entière de la racine carrée, et tu élimines BEAUCOUP de cas inutiles simplement en retirant les multiples de 2, 3, 5, et 7 dans les tests.

Ben faut voir, tu vois ca comment :
-la boucle les sautes (deja les multiples de deux en ne faisant pas ++ mais +=2 pour l'incrementation)?
-On applique les regles de divisibilité qu'on connait, du genre si le nombre ce finit par un nombre pair pour 2, un 0 ou un 5 pour 5, etc... Reste a savoir si c'est plus rapide que de diviser par le nombre lui même ( 2 , 3 , 5...). Car la fonction dès qu'elle trouve un diviseur renvoie immédiatement 0 et se stoppe. Je pourrait pas dire, a vous de voir.

La principale "optimisation" c'est la racine carrée. Pour écarter les multiples de 2, 3, 5 et 7, finalement ce n'est pas si rapide que ça : les critères de divisibilité ne sont pas commodemment applicables (à la rigueur, faudrait en chercher en base 2 mais pour quel bénéfice ?), et sinon, diviser directement a un coût (la division est l'opération arithmétique la plus couteûse et de loin). Sinon, comme Pole disait, le traitement du plus grand nombre premier inférieur à <math>\(2%5E%7B64%7D-1\)</math>, à savoir 18446744073709551557, se traite par l'algo naïf en un petit paquet de secondes.

EDIT Balise math

Citation : candide

La principale "optimisation" c'est la racine carrée.

Oui, je vais apprendre comment la mettre correctement et l'utiliser.

Citation : candide

Pour écarter les multiples de 2, 3, 5 et 7, finalement ce n'est pas si rapide que ça : les critères de divisibilité ne sont pas commodemment applicables (à la rigueur, faudrait en chercher en base 2 mais pour quel bénéfice ?), et sinon, diviser directement a un coût (la division est l'opération arithmétique la plus couteûse et de loin)

Ben on peut peut etre passer sur une incrémentation de 2 quand on est sur d'etre sur un impaire non? Enfin , ca fera toujours ca de pris non?

Citation : candide

Sinon, comme Pole disait, le traitement du plus grand nombre premier inférieur à </math>2^{64}-1</math>, à savoir 18446744073709551557, se traite par l'algo naïf en un petit paquet de secondes.

Oui, c'est sur, ca prend du temps (je dirai plusieurs minutes a vu d'oeil). (attention tu as mis 2 balises "math" de sortie ).
Mais justement, supposons que ce nombre soit premier. Imaginons qu'on prenne un tableau des 10 000 premiers entiers (ca va a 101 000 et des poussieres, je crois). Et bien grâce au tableau on evitera un nombre conséquent de diviseur inutiles (pas premiers) non? Surtout que la racine de ce truc doit quand même pas etre tout petite. Et surtout, si on en fait plusieurs dans ce genre là, non?
Enfin je suis d'accord sur le fait qu'il y a bien mieux comme optimisation.

Citation : Toineo

Ben on peut peut etre passer sur une incrémentation de 2 quand on est sur d'etre sur un impaire non? Enfin , ca fera toujours ca de pris non?

Bien sûr mais d'ailleurs on doit pouvoir généraliser à 3, 5, 7 et 11 en maintenant un tableau et ainsi éviter les divisions couteuses.

Citation : Toineo

Imaginons qu'on prenne un tableau des 10 000 premiers entiers (ca va a 101 000 et des poussieres, je crois)

cf. le site : nth prime

Citation : Toineo

Mais justement, supposons que ce nombre soit premier. Imaginons qu'on prenne un tableau des 10 000 premiers entiers (ca va a 101 000 et des poussieres, je crois). Et bien grâce au tableau on evitera un nombre conséquent de diviseur inutiles (pas premiers) non?

Oui, mais à quel prix ? Tu vas devoir dresser une grosse table des nombres premiers jusqu'à la racine carrée juste pour savoir si UN (seul) nombre est premier, ça ne vaut pas le coup.

Citation : candide

Bien sûr mais d'ailleurs on doit pouvoir généraliser à 3, 5, 7 et 11 en maintenant un tableau et ainsi éviter les divisions couteuses.

Bonne idée, mais comment fais tu? J'avoue que je vois pas trop...
Si possible mets nous un ptit code-exemple, c'est plus simple...

Citation : Candide

cf. le site : nth prime

J'y était presque : The 10,000th prime is 104,729.

Citation : candide

Oui, mais à quel prix ? Tu vas devoir dresser une grosse table des nombres premiers jusqu'à la racine carrée juste pour savoir si UN (seul) nombre est premier, ça ne vaut pas le coup.

Non bien sûr pour un nombre ca sert a rien, et le prog est même plus long : car ces diviseurs premiers on les teste 2 fois, une pour le tableau + une pour le nombre. Et comme pour le tableau on teste TOUS les nombres jusqu'au Nieme premier, on se retrouve a la fin en ayant testé tous les nombres jusqu'a la moitié (bientôt la racine...) + 1 fois les X premiers nombres premiers.
Mais pour plusieurs c'est déjà plus utile.

Evidemment, ca depend aussi de la memoire disponible : par exemple les 10 000 premiers n'occupe que 40 Ko, soit quand même pas beaucoup...

Citation : Toineo

Citation : candide

Bien sûr mais d'ailleurs on doit pouvoir généraliser à 3, 5, 7 et 11 en maintenant un tableau et ainsi éviter les divisions couteuses.

Bonne idée, mais comment fais tu? J'avoue que je vois pas trop...
Si possible mets nous un ptit code-exemple, c'est plus simple...

J'ai pas trop le temps de regarder en détail mais l'idée est simple : tu maintiens un tableau de 4 entrées (correspondant à 3, 5, 7 et 11) et tu y maintiens le reste de la division de d en faisant des incréments de 1 dans chaque entrée du tableau sachant que lorsque tu arrives à 3 pour la première case du tableau par exemple, il faut mettre 0 et de même pour les autres entrées. Ça c'est pour l'idée mais je sais même pas si c'est efficace et et si ça l'est algorithmiquement, pour que ça le soit dans le codage, l'expérience montre qu'il faut pas mal réfléchir.


Un code très semblable à celui déjà donné en lien donne pour le plus grand entier premier représentable dans mes unsigned long long (20 chiffres décimaux) le résultat suivant :

Pour un intervalle je ferai un crible d'Erathostène généralisé (c'est beaucoup plus rapide par contre les limites seront plus basse : avec 1 Mo on peut faire jusqu'à 10^12, avec 100 Mo -> 10^16).
Sinon quelques tests de Rabin-Miller plus un bon coup de courbes elliptiques et c'est bon (par contre le niveau de maths, ouch)
Pour les 100 chiffres de l'applet il faut quelques heures maximum pour factoriser un nombre de cette taille avec un programme optimisé.

Citation : Pole

(par contre le niveau de maths, ouch)

Oui oui !
C'est pas la peine que je fasse ca si je comprend pas...

Et puis de toute facon on est limité a environ 10^18 ici, donc ca prend du temps mais pas trop trop non plus...