Nombres premiers : Algorithme Algibri
dans Arithmétique
....
Cette discussion a été fermée.
Réponses
après avoir essayé cet algorithme sur les entiers jusqu'à 1000, il fonctionne et les donne tous (sauf 2, évidemment). Je ne sais pas s'il est de ton invention ou pas, mais d'autres le sauront sûrement.
Il présente quand même un gros inconvénient : la liste à vérifier devient de plus en plus longue, et il est donc d'une efficacité qui se réduit au fur et à mesure de la progression.
Enfin, d'un point de vue très naïf, je ne comprends pas pourquoi tu parles de p+(2*p) au lieu de 3p ???
Cordialement,
Sébatiduroc.
En fait, tu calcules les multiples des nombres premiers que tu trouves au fur et à mesure. Donc effectivement, j'ai peur que cela ne sera pas très efficace dès que tu voudras chercher des grands nombres premiers.
quand tu arrives à 47 tu incrémentes de 2, 49 n'est pas dans la colonne de gauche que fais tu ?
en gros que fais tu pour les entiers qui sont des produits de p à la puissance n
> bonjour
>
> quand tu arrives à 47 tu incrémentes de 2, 49
> n'est pas dans la colonne de gauche que fais tu ?
>
>
> en gros que fais tu pour les entiers qui sont des
> produits de p à la puissance n
Le 49 y est
7 + (2*7) = 21
21 + (2*7) = 35
35 + (2*7) = 49
Tu as dû commettre une erreur quelque part.
Quand tu rencontres un nombre et qu'il figure dans la base, tu le supprimes et le remplace par la "prochaine station" :
en ajoutant à ce nombre 2 fois le nombre premier qui lui correspond
Si c'est le 23 avec en en face 69
tu supprimes 69 et tu remplaces par 69 + (2*23) = 115.
car le tien en plus il réecrit des multiples de trois inutilement exemple avec 15, pourquoi faire deux opération pour écrire dans ta base de donné 21,25 tu vas donc faire le travail inutilement en inscrivant de nouveaux muliple de trois , puis 5 ,puis 7 etc etc :
fixe une borne et chaque nombre premier élimine ses multiple en rayant tous les 3 nombre ,5,7 etc .
il n'y a pas d'écriture il y a juste à suprimer les multiples,tous les P nombres, Eratosthène!
il n'y a donc pas de vérification à faire dans une base de donnée qui comporterra des multiples en double ou en triple inutilement, qui va très vite saturer ta mémoire et qui de toutes les façon serra borné par ta limite.
3 5 7 . 11 13 . 17 19 . 23 . . 29 31 .. en définitive tes nombres P agissent comme une sonde numérique chaque cible marquée est suprimé et libère de la mémoire. toi tu fais le contraire tu alourdis et tu encombres la mémoire. pour la même limite .
il existe des bases de données de plus de 5 000 000 000 000 de nombres premiers ce qui n'apporte strictement aucun intérêt pour tester de grand nombres. On ne s'en sert pas!
Je ne suis pas programmeur. Je présente un algo qui n'est aucunement l'algo d'Ératosthène, ni celui de Sandaram.
L'originalité de l'algo réside en deux choses :
- la possibilité de tourner en continu (cumulatif)
- la possibilité d'une programmation parallèle
Les questions purement informatiques de choix d'algo de tri, de gestion d'une base de données etc... ne sont pas de mon ressort. Je n'ai aucune compétence en la matière.
Sauf que je suis convaincu que mon approche constitue un plus dans la dizaine d'algos de génération de nombres premiers.
Ne pense surtout pas que c'est un algo achevé.
Les programmeurs travaillent toujours AKS et cherchent à l'implémenter.
Amusez-vous bien et joyeuses fêtes.
Il est rare que j'intervienne sur ce genre de remarque alors profites en
>Vu le peu d'intérêt que ça suscite, je préfère arrêter de monologuer comme un fou.
Ce n'est pas parce qu'on ne participe pas, qu'on n'est pas intéressé !
Perso je ne participais pas parce que je n'avais rien à dire d'intéressant !
D'ailleurs je n'ai toujours rien d'intéressant à dire...
Voili voilà c'était la reflexion du soir.
Comme dit mon père,"amis du soir, bonsoir".
J'ai pas appronfondi a fond ton algo mais cela ressemble fort à une crible.
L'utilisation d'une base de données est de toute façon proscrite. Des telles tables seraient en RAM, en mémoire, à l'accès bien plus rapide qu'une base de données.
Quand aux limites, elles sont celles de la machine (quantité de RAM, vitesse CPU...) sur laquelle on ferait tourner ton algo.
Le mieux pour toi, c'est de le coder, en python par exemple ou autre...
Mais ça va être dur de faire mieux que l'ECPP ou que le "General number field sieve".
Dans les pgm de décomposition des nombres premiers en poids*niveau+saut, on utilise un crible d'Eratosthène pour générer les nombres premiers et un test probabiliste, surement un "Rabin-Miller", (une classe java bien pratique...) et ça nous suffit amplement.
C'est un domaine très dur auquel tu t'attaques.
Bon courage et si tu veux des conseils pour le développement n'hésite pas à me contacter.
Rémi
J'ai déjà dit que je n'étais pas programmeur.
De toute façon, j'ai envoyé l'algo à un ami programmeur (très occupé il est vrai) en lui laissant un ou deux mois pour me répondre.
Merci pour tout.