Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#26 25-11-2020 23: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
#28 26-11-2020 11: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 11:47:09)
Hors ligne
#29 26-11-2020 11: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 12: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
#33 26-11-2020 13:04:17
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 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 13:44:48
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 13: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 15:44:12
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 19:09:49
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 19:12:40)
Hors ligne