Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#26 25-11-2020 22:38:28

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Bonne nuit  48PierrelePetit
Moi même je ne peux expliquer le raisonnement mais la réalité est la .... et ça marche !
Essayons donc tous de comprendre comment et pourquoi ça marche.
J'ai remodelé l'algorithme et gagné encore du temps d'exécution

@ plus et merci de vos participations

Hors ligne

#27 26-11-2020 09:01:49

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Nouvelle logique pour calculer les nombres premiers

Bonjour Omhaf,

Et si tu nous disais pourquoi 12 ? pourquoi pas 6 ? 14 ? 18 ?
Tu n'as pas choisi 12 par hasard, alors ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#28 26-11-2020 10:44:57

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Bonjour
élimine la partie inutile pour voir si ça marche c'est simple non ?
La division par 12 filtre beaucoup de nombres et soulage la vérification ultérieure
Comparez les temps d'exécution des algorithmes classiques et de celui-ci
J'ai encore simplifié l'algorithme pour gagner plus de temps. je posterai plus tard.
Merci

Dernière modification par Omhaf (26-11-2020 10:47:09)

Hors ligne

#29 26-11-2020 10:56:59

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Re Bonjour
Voici un exemple expliquant l'utilité de la division par 12
admettons que le compteur a passé 19 et retenu son carre cad AncienCarre=361
la boucle sautera à 21
Carre =21² = 441
Différence=441-361=80
80/12  n'est pas entier on saute au suivant en l'occurrence 23
23²=529
Différence = 529-361 =168
Oui 168/12 = un entier cad  14
on retient 23 pour les verifs  ultérieures

Hors ligne

#30 26-11-2020 11:13:19

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Bonjour yoshi
Pour répondre à ta question yoshi lis bien ce qui suit stp
Je déclare  que la différence entre les carrés de 2 nombres premiers divisée par 12 donne   toujours un entier
si cette déclaration s'avère vraie et est inédite je  te prie de la publier en mon nom et merci

Hors ligne

#31 26-11-2020 11:45:07

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Re bonjour
Testé avec chrono
50000 nombres premiers   (dernier =611953) en 1mn 33 s 92/10

Hors ligne

#32 26-11-2020 11:57:37

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Merci  pour ton indulgence 48PierrelePetit

Hors ligne

#33 26-11-2020 12:04:17

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Nouvelle logique pour calculer les nombres premiers

Re,

la différence entre les carrés de 2 nombres premiers divisée par 12 donne toujours un entier

Non, pas toujours...
Contre exemples :
$5^2-3^2=25-9=16$ et $16/12$ n'est pas entier...
$7^2-3^2=49-9=40$ et $40/12$ n'est pas entier...
Désolé, ami Omhaf... Console-toi, 48PierrelePetit a aussi énoncé une proposition fausse...

J'ai retravaillé ton Algorithme, je l'ai élagué de choses encombrantes (et qui ne servaient qu'à le ralentir), voilà ce que j'en ai fait en utilisant la "fonction" préexistante en Python : is_integer().
Pourquoi ?
Parce que si je demande à Python quel est le type de sqrt(4)  il me répond float donc pas entier, parce que le résultat est 2.0
Cette "fonction" contourne ce problème et donne la bonne réponse.
Et donc, je n'ai plus besoin de tester la partie décimale pour savoir si le résultat est entier ou non.
J'ai inclus un chronomètre qui m'a permis de voir que j'ai divisé le temps de calcul par 3,4.

from math import sqrt
from time import time

Primes=[2]
debut=time()
for MonNombre in range(1,1000001,2):
    Result=1
    if not sqrt(MonNombre).is_integer():      
        Xetendue=int(sqrt(MonNombre))+1
        for compteur in range(3,Xetendue,2):
            if MonNombre%compteur==0:  
                Result=0
        if Result:
            Primes.append(MonNombre)

print(time()-debut, "s")
print(Primes)
print(len(Primes))

Recherche des premiers entre 1 et 1000000 : 32 s pour 78498 nombres trouvés...

14,5 s pour les 50000 premiers trouvés...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#34 26-11-2020 12:44:48

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Nouvelle logique pour calculer les nombres premiers

Re,

La différence entre 2 carrés de nombres premiers différents > 3 est donc toujours un multiple de 12

Si tu entends que les deux premiers sont tous deux >3, alors mes contre-exemples ne marchent plus...
Différents est inutile : 0 est un multiple de 12 (et de n'importe quoi d'autre). Stricto sensu, même en ne le précisant pas, la propriété est vraie pour une différence nulle.
Préciser "différents" laisse entendre que sinon, ce ne serait pas vrai...

Dont acte, j'ai écrit trop vite : je ne suis pas infaillible, moi. Surtout quand je fais plusieurs choses à la fois.
Et puis, avec l'âge, on devient sénile, c'est bien connu...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#35 26-11-2020 12:46:16

Omhaf
Membre
Inscription : 16-01-2020
Messages : 225

Re : Nouvelle logique pour calculer les nombres premiers

Re
Merci yoshi oui il fallait prendre en considération les avantages que Python offre car Windev n'est qu'un AGL (générateur d'applications  de gestion  et administratives)
en plus avec une machine 64 bits et une configuration optimale de la RAM les résultats seront meilleures
Pour la divisibilité par 12, oui il faut déclarer un seuil à partir duquel l'assertion est vraie  (à partir de 5 et 7   49-25= 24 = 2*12)
Enfin permets moi de te remercier pour tes sympathiques interventions

Hors ligne

#36 26-11-2020 14:44:12

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Nouvelle logique pour calculer les nombres premiers

Bonjour,

Tu peux tout aussi bien te lancer dans Python aussi.
Le langage est libre et gratuit, il dispose d'une quantité assez phénoménale de librairies (programmes additionnels si u préfères) tierces qui en les installant avec le Python de base (à la base déjà bien large d'ailleurs), tu disposes de tas de fonctions supplémentaires...
J'ai une machine 64 bits et 16 Go de RAM, ce qui n'empêcherait pas mon script dxe fonctionner tel quel sur une machine 32 bits avec 8 Go de RAM...
L'avantage de Python est qu'il est clair à la lecture...
L'inconvénient, c'est que, langage interprété, il est sensiblement plus lent que C ou C++ par exemple...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#37 26-11-2020 18:09:49

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : Nouvelle logique pour calculer les nombres premiers

Bonsoir à tous
@Yoshi je pense que pour l'optimiser il faut déjà éliminer les multiples de 2,3,et 5  travailler avec les entiers des 8 famille 30k + i , avec appartenant à (1,7,11,13,17,19,23,29) ce qui supprime 73,666....% des entiers naturels

Ce qui donne:
[   1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 ]
[ 31 ,37, 41 , 43 , 47 , 49 , 53 , 59 ]
etc...
@Omhaf.
peux tu donc essayer avec ta programmation... voire le temps que cela donne ; Sinon en python par Yoshi...

car regarde ce que donne mon algorithme écrit par Yoshi en Python :
pout N 1000 020; avec la Fam 3k + 7

===== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ====
Donnez N: 1000020
Nombre premiers criblés famille 7 : 9812 ----- 0.0
--- Temps total: 0.01 sec ---

Donc tu vois pour les 8 familles cela donne 0,01 seconde * 8 = 0,08 secondes ....

Donnez N: 1000020
Nombre premiers criblés famille 1 : 9807 ----- 0.0
--- Temps total: 0.01 sec ---
>>>
Donnez N: 1000020
Nombre premiers criblés famille 11 : 9810 ----- 0.0
--- Temps total: 0.01 sec ---
Donnez N: 1000020
Nombre premiers criblés famille 13 : 9826 ----- 0.01
--- Temps total: 0.01 sec ---

passons à n = 100 000 020

===== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ====
Donnez N: 100000020
Nombre premiers criblés famille 7 : 720270 ----- 0.4
--- Temps total: 0.4 sec ---

soit pour les 8 familles : 3,2 secondes... en Python .
De plus tu va très vite saturer ta mémoire si tu dois écrire tous les nombres pour les tester au lieu de sauter par pas de P ("un nombres premiers, inferieur à racine de N") à partir de l'index du produit  etc...

C'est peut être originale comme le dit Yoshi....(d'utiliser modulo 12)  mais cela n'apportera rien de nouveau dans le criblage des nombres premiers.

Dernière modification par LEG (26-11-2020 18:12:40)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante moins cinquante deux
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums