Bonjour, je souhaiterais poser une question a propos de la technique de division par tout les nombres avant n pour verifier si n est premier. Je mexplique : si je prend 500 je le divise par 1;2;3... jusqua 499. Ma question est : peut on prendre comme limite la racine de 500 et donc diviser 500 par 1;2;3 jusqua la partie entiere de V500
Dernière modification par RezCray1 ; 18/04/2014 à 23h50.
Bonsoir,
La réponse est oui, ... par contre il n'est pas nécessaire de tester tous les nombres entiers mais uniquement les nombres premiers.Envoyé par RezCray1
Par exemple pour savoir si 101 est un nombre premier, tu ne vas pas tester 2, 3, 4, 5, 6, 7, 8, 9 et 10, mais uniquement 2, 3, 5 et 7 (inutile de tester 4=2x2 car 2 a déjà été testé, inutile de tester 6=3x2 car 3 et 2 ont déjà été testés, etc ...)
Cordialement.
N.B. : Contrairement à ce que tu écris, aucun test à faire avec 1 !
Dernière modification par PlaneteF ; 19/04/2014 à 00h20.
Oui tu as absolument raison mais jecrivais cela dans un contexte de programme sur texas instrument : mon programme utilise un algorithme ou on tape la valeur a tester puis la calculatrice calcule la racine de ce nombre et ordonne de diviser par tout les nombres ( je ne sais pas choisir "uniquement nombre impair")en commencant par deux jusqua la partie entiere de la racine du nombre choisis. Le probleme etant que, pour les petits nombres l'algorithme fonctionne bien mais quand jarrive a de grands nombre la calculatrice ne me donner plus premier alors que ce sont des nombres premiers.
Il faudrait voir le programme ...
mais il est plus simple de tester la division par 2 puis diviser seulement par les impairs.
Pour les très grands nombres, ta calculette ne faisant plus du calcul "exact", tu peux avoir des ennuis, effectivement. mais sur la plupart des calculettes habituelles, on peut utiliser un test simple de divisibilité pour des nombres jusqu'à 12 à 14 chiffres (donc des diviseurs à 6 ou 7 chiffres).
Cordialement.
Daccord merci, jai reussi a remedier au probleme en partant dun diviseur C=2 puis lui faire prendre la valeur 1 et ensuite additionner 2 a chaque division pour navoir que des nombres impairs pour pouvoir acceler le calcul! Je souhaiterais que ce nombre C ne soit que constitue de nombre premier mais il ny a evidemment pas de formule pour avoir que des nombres premier et je ne pense pas que ma calculatrice a une fonction "uniquement nombre premier". Merci pour ta reponse gg0 je navais pas envisage le fait que la callculette fonctionne en exposant. Merci je me contenterais de ce que jai qui nest deja pas mal!!
Vous avez pas une idee pour alleger les calculs ? Car ppur determiner que 1 000 000 007 est premier ca prend 10 minutes. Sachant que pour linstant mon programme divise ce nombre par 2 puis 3 puis 5 puis 7 puis 9 ect jusqua la partie entiere de la racine de 1 000 000 007
En testant 2, puis les impairs à partir de 3, et en passant au quotient à chaque fois, on obtient tous les diviseurs premiers et eux seuls. Les impairs non premiers n'apparaissent pas.
par exemple pour 102 :
Divisible par 2 ? Oui on affiche 2 puis on continue avec 51.
Divisible par 2 ? Non
Divisible par 3 ? Oui; on affiche 3 puis on continue avec 7.
Divisible par 3 ? Non.
Divisible par 5 ? Non.
Divisible par 7 ? Non.
Divisible par 9 ? Non.
...
Divisible par 17 ? Oui. On affiche 17 et comme le quotient est 12, on s'arrête.
Le passage par 9 ne sert à rien car divisible par 9, c'est divisible au moins 2 fois par 3, qu'on a traité auparavant.
On peut faire mieux en testant 2 et 3, puis les nombres de la forme 6n+1 ou 6n-1.
Cordialement.
Je ne comprend pas tres bien ce que tu veux dire, car si je prend 1 000 000 002 mon programme trouve instantanement car cest divisible par 2, il na pas besoin de tester 500 000 001 par 3. Je ne pense avoir compris ce que tu as voulu dire
Existe t-il un nombre qui n'a pour diviseurs que des nombres premiers ? Pour que je demande a la calculatrice de diviser mon nombre a tester que par, par exemple " 2*3*5*7*11*13*17*19*23*29*31.. "
EDIT : je vien de me rendre compte que cest debile laissez tomber
Dernière modification par RezCray1 ; 19/04/2014 à 12h43.
La dernière réponse de gg0 c'est pour afficher la décomposition en facteurs premiers du nombre, dans l'exemple 102=2*3*17. Évidemment, si tu veux juste déterminer si le nombre est premier ou pas, comme tu dis, on n'a pas besoin de faire ca.
Effectivement RezCray1,
je suis parti sur un autre programme que celui que tu voulais.
Il existe des méthodes pour alléger les calculs, mais qui relèvent de la théorie des nombres (arithmétique moderne) et qui sont difficilement explicables à petit niveau (mais tu peux aller voir sur internet "algorithmes de primalité").
Ton programme de calculatrice est peut être modifiable pour l'accélérer au niveau du test de division, car tu procèdes quand même ici à presque 32000 divisions.
Cordialement.
Cordialement.
Merci beaucoup de vos réponses, (j'ai mis un peu de temps à répondre). J'ai finalement opté pour l'option "naive", le diviseur ne peut prendre que des valeurs impair et sous la racine du nombre a tester. Pour 1 000 000 000 il ne fait qu'une division puisque le diviseur commence par 2, ca se complique quand c'est un nombre premier que l'on teste comme 1 000 000 007. Ducoup je voudrais savoir si on pouvait estimer que _au bout d'un certain nombre de diviseur utilisé_ une probabilité que le nombre soit premier. Par exemple pour un nombre comme 1 000 000 007 au lieu de faire environ 16 000 divisions il en fait 700 puis affiche "une probabilité d'erreur de 1-(700/16000) x 100 %". En gros je prend 700 comme limite de diviseurs (le nombre dont la racine divisé par deux est égale à 1000 est (700x2)² est 2 000 000; ce qui me semble une bonne limite de premier).
Ou encore afficher au fur et à mesure que le programme calcule la probabilité ? Je voudrais enfait savoir si on pouvait estimer aussi facilement la probabilité qu'un nombre soit premier grâce à "l'option naive"; si certains diviseurs près de la racine, près de 0 ect sont plus important c'est plus difficile
Dernière modification par RezCray1 ; 27/04/2014 à 23h22.
