J'essaie de terminer 10ème problème du projet Euler , mais le code que j'ai actuellement prend tellement beaucoup de temps, il n'a pas été en mesure de se terminer.
J'ai regardé autour de moi, mais je n'ai pas été en mesure de trouver comment rendre le code plus court.
Voici le code que j'ai:
def IsPrime(num):
for i in range(2, num/2):
if num % i == 0:
prime = False
return prime
prime = True
return prime
def SumOfPrime(limit):
primesum=2+3 #For some reason my prime finder doesn't allow numbers below 5
for check in range(5,limit):
prime=IsPrime(check)
if prime == True:
primesum += check
return primesum^2
print(SumOfPrime(2000000))
La bonne réponse devrait être 142913828922 , cependant, comme mentionné précédemment je ne n'obtiens pas une sortie entièrement. Existe-t-il un moyen de rendre ce code plus rapide?
3 Réponses :
Quelques conseils pour accélérer votre mise en œuvre:
Si vous voulez un algorithme plus efficace, veuillez consulter https://en.wikipedia.org/wiki / Sieve_of_Eratosthenes
il faut maintenant 32,98 secondes pour que cela se termine. J'aimerais voir un plus vite algorithme
Vous devez utiliser un Tamis d'Ératosthène . En ignorant cela, cette retouche devrait vous faire gagner moins de 10 secondes:
def isPrime(number): if number <= 2: return number == 2 if number % 2 == 0: return False for divisor in range(3, int(number ** 0.5) + 1, 2): if number % divisor == 0: return False return True def sumOfPrimes(limit): return sum(number for number in range(limit) if isPrime(number)) print(sumOfPrimes(2000000))Traitez les nombres pairs comme un cas particulier dans
isPrime () puis traiter simplement les diviseurs impairs . L'utilisation d'une compréhension ou d'une expression de générateur fait descendre une plus grande partie de votre code en boucle au niveau C et vous permet généralement d'obtenir un peu plus de vitesse.
Après quelques tests, j'ai utilisé le même code avec la seule différence if number == 2: return True juste en testant les nombres de 1-10000, le code s'est terminé en 13,549189329147339 sec Lors du test avec le code suivant: def IsPrime (num): for i in range (2, int ((num ** 0.5) +1)): if num% i == 0: return False return True Cela prend 13.15842890739441 < / code> secs Je me demande pourquoi le premier est à peu près le même que le second, même s'il n'analyse que la moitié des nombres ... Quelqu'un a-t-il une raison à cela?
@ Thomas.B, tester des nombres jusqu'à 10 000 ne devrait prendre qu'une fraction de seconde, pas 13 secondes. Le changement que vous avez effectué ne montre aucune différence de synchronisation sur mon système car la plage de nombres est trop petite. À environ 100 000, les surfaces de différence.
Je viens de remarquer l'erreur. Je voulais écrire 1 000 000. Je ne sais pas comment j'ai changé autant le nombre de zéros.
Utilisez le tamis d'Ératosthène:
$ python Python 2.7.13 (default, Mar 13 2017, 20:56:15) [GCC 5.4.0] on cygwin Type "help", "copyright", "credits" or "license" for more information. >>> def sumPrimes(n): ... i, p, ps, m, sum = 0, 3, [2], n // 2, 2 ... sieve = [True] * m ... while p <= n: ... if sieve[i]: ... sum += p ... for j in range((p*p-3)/2, m, p): ... sieve[j] = False ... i, p = i+1, p+2 ... return sum ... >>> from time import time >>> start = time(); print sumPrimes(2000000); print time() - start 142913828922 0.262000083923
Environ un quart de seconde sur ma machine.
Sur ma machine, en Python 3, cela explose avec, "TypeError: l'objet 'float' ne peut pas être interprété comme un entier". En Python 2, il renvoie le mauvais résultat pour n == 2 ou moins.
Il n'y a aucun flottant n'importe où dans l'algorithme, sauf si vous passez un flottant comme argument n . J'ai Python 2.7.13 installé. Ça fonctionne bien. sumPrimes (2) renvoie correctement 2. Je n'ai pas pris la peine de vérifier les erreurs des cas pour n inférieur à 2 ou pour n un flottant. J'ai modifié ma réponse pour afficher les en-têtes et les informations de synchronisation.
En Python 3, (p * p-3) / 2 est une valeur à virgule flottante et la transmettre à range () génère l'erreur que j'ai citée ci-dessus. (Pas parce que n est un flottant.) Considérez plutôt // (division entière). Si vous suivez le lien de l'OP vers le problème d'Euler, la fonction additionne les nombres premiers inférieurs à n . Ainsi, le résultat pour n == 2 est 0 , votre résultat 2 est incorrect.
@cdlane la réponse indique clairement qu'il s'agit d'un code Python 2.7.13, alors pourquoi devrions-nous nous préoccuper de Python 3? Quant au 2, il peut être facilement en boîtier spécial, donc ce n'est pas un problème non plus, oui? J'ai suivi le lien, et ce qui est demandé il y a une solution pour 2 000 000, pas pour 2.
@WillNess, la réponse n'a pas clairement indiqué que c'était du code Python 2.7.3 jusqu'à ce que après j'écrive mon commentaire. Et les deux problèmes peuvent être facilement résolus sous Python 2.
@cdlane ils n'ont cependant pas besoin d'être corrigés sous Python 2.
for i in range (2, num / 2):Je définirais la limite supérieure àint (sqrt (num)) + 1, je pourrais aussi donner un plus efficace algorithme mais vous voulez accélérer celui-ci, non?Cela a beaucoup aidé! J'obtiens le résultat correct et il faut maintenant
32,98 spour qu'il se termine. J'adorerais voir un algorithme plus rapide car il n'est bien sûr pas parfait.Hmm, vous pouvez également enregistrer les nombres premiers trouvés dans une liste et vérifier si un nombre est un nombre premier divisant uniquement par les nombres premiers que vous avez trouvés précédemment, si vous voulez une meilleure façon de trouver les nombres premiers en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Ça a l'air intéressant, merci beaucoup! Peut-être publier ces deux choses comme réponse afin que je puisse marquer la question comme résolue? =)
Puisque 2 est le seul nombre premier pair, dans votre méthode
IsPrime, vous pouvez vérifier 2 comme diviseur, puis vérifier uniquement les diviseurs impairs: 3, 5, 7, 9,11, ... jusqu'au racine carrée. Pas aussi efficace qu'un tamis, mais devrait réduire de moitié le temps passé à vérifier un nombre.