Un nombre premier est un entier égal ou supérieur à ** 2 et ne contenant que des fractions évidentes. La chose évidente ici est 1 et moi-même. En d'autres termes, n est appelé un nombre premier lorsqu'il n'y a que 1 et n dans lequel n ÷ m est un entier pour un entier n.
C'est parce que lorsque vous donnez un produit à un ensemble d'entiers positifs, la ** base ** est un nombre premier. Quiconque a étudié les mathématiques comprendra à quel point les bases sont importantes. Au fait, si l'opération est somme, une base suffit (seulement 1 peut rendre tous les entiers positifs)
(À propos, dans l'ancien temps où le concept de base n'était pas maintenu, il semble que les nombres premiers n'étaient pas si importants. Il était reconnu qu'il y avait de tels nombres.)
Le Dr Euclidien a prouvé que le nombre de nombres premiers est infini depuis longtemps. À une époque où il n'y avait pas de concept d'infini, il a écrit dans la phrase: "Si le nombre de nombres premiers est un nombre, il y a plus de nombres premiers que cela." De nos jours, le concept commode de l'infini est en place, mais qui était M. Euclidien qui a intuitivement compris le concept de l'infini si précisément à l'époque où il n'existait pas?
Il s'avère que le nombre total de nombres premiers est infini. Mais combien de nombres premiers y a-t-il en nombres de 1 à n? A été résolu en 1896 avec un problème assez difficile. (Maintenant, il y a un éclairage élémentaire, mais ce n'est que élémentaire et c'est assez difficile à comprendre) De plus, il ne s'agit que d'un «ratio» et la formule exacte «combien» est encore inconnue (probablement). Cependant, si vous donnez n spécifiquement, vous pouvez compter les humains et les chiens avec une immense compréhension. Parce qu'il suffit de diviser par tous les nombres inférieurs ou égaux à n et de s'assurer qu'il n'y a que des fractions évidentes. Vous pouvez le faire si vous faites de votre mieux. Et il semble qu'il y avait quelque chose comme une table de nombres premiers dans les années 1800. Je ne connais pas la limite supérieure du nombre de nombres premiers à bord. Cependant, il semble qu'il y ait pas mal d'erreurs, et le Dr Euler a prouvé en 1797 le théorème que ** 1000009 n'est pas un nombre premier **. En d'autres termes, "que n soit un nombre premier ou non peut être calculé théoriquement si vous faites de votre mieux, mais c'est une erreur". Ensuite, vous pouvez calculer quoi faire à la place avec un ordinateur.
Cette fois, le but n'est pas un programme qui détermine si n est un nombre premier, mais un programme qui trouve combien de nombres premiers sont compris entre ** 1 et n **.
La définition que n est un nombre premier est qu'il n'y a rien de divisible par un entier de ** 2 à n-1 **. Ensuite, implémentez-le par programme
def number1(n):
cnt=1
for i in range(2,n+1):
for j in range(2,i):
if i%j==0:
break
elif i%j!=0 and j==i-1:
cnt+=1
return cnt
Étant donné que le processus de 2 ne s'est pas bien déroulé, j'ai défini cnt = 1 à l'avance, mais je pense que cela ressemblera à ceci s'il est mis en œuvre docilement. Même cela est extrêmement plus rapide que les humains, mais au moins je veux faire jusqu'à 1000009 de M. Euler à une vitesse explosive. C'est trop tard. Pensons aux plans d'amélioration
Lorsque l'on considère s'il s'agit d'un nombre premier, les nombres pairs autres que 2 ne sont évidemment pas des nombres premiers, n'est-ce pas? Si oui, excluons-le.
def number2(n):
cnt=1
for i in range(3,n+1,2):#← Seulement cela a changé
for j in range(2,i):
if i%j==0:
break
elif i%j!=0 and j==i-1:
cnt+=1
return cnt
Il ne vous reste plus qu'à penser aux probabilités! Le nombre de calculs a simplement été divisé par deux! Encore une chose ici ... Si le nombre à diviser n'est qu'un nombre impair, n'est-il pas possible de ne diviser qu'un nombre impair? ......
def number3(n):
cnt=2#point de changement
for i in range(3,n+1,2):
for j in range(3,i,2):#point de changement
if i%j==0:
break
elif i%j!=0 and j==i-2:#point de changement
cnt+=1
return cnt
Avec cela, tous les nombres à diviser et le nombre à diviser sont impairs à l'exception de 2! Le nombre de calculs est simplement de 0,25 fois! Cependant, il est encore tard. Je me fâche contre DI ○. Pensons s'il y a des déchets
Par exemple, si n ne cassait pas à 5, serait-il cassé à 25? La réponse est non. Si n ÷ 25 = entier Ce sera n ÷ 5 = 5 * entier. En d'autres termes, c'est une perte de temps de diviser par 9 même si cela ne divise pas par 3, ou par 15 même si cela ne divise pas par 3 et 5. En d'autres termes, ** seuls les nombres premiers sont nécessaires pour diviser ** Cependant, il ne sert à rien d'utiliser une liste de nombres premiers lorsque vous voulez trouver un nombre premier, alors faisons vous-même une liste de nombres premiers. Commencez par reconfirmer la définition Je pensais qu'il n'y avait pas de nombre premier où n est divisé par un nombre de 2 à n-1 pour devenir un entier. Pensons que ** n n'est divisible par aucun nombre premier inférieur à n **! La définition est la même pour les deux, mais si vous l'écrivez par programmation, cela changera beaucoup! Si vous écrivez un programme avec l'idée que le nombre qui peut être divisé n'est qu'un nombre impair
def number4(n):
li=[2]
for i in range(3,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and j==li[-1]:
li.append(i)
return len(li)
Je pense que ce sera! C'est beaucoup plus rapide qu'au début! Il y a encore des déchets évidents.
Vous êtes en train de vérifier si n ÷ nombre premier est un entier. Quelle est la valeur minimale de cet "entier"? ...... ** 2 **, non? En d'autres termes, si n vaut 100 ou quelque chose du genre, vous n'avez pas à le diviser par 53 ...? Car évidemment 100 ÷ 53 est inférieur à 2. Ensuite, vous pouvez l'utiliser pour économiser encore plus de déchets.
def number5(n):
li=[2]
for i in range(3,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and 2*j>i:#point de changement
li.append(i)
break #point de changement
return len(li)
Mais vous pouvez toujours réduire la portée!
Supposons que n n'est pas divisible par tous les ** nombres premiers inférieurs ou égaux à √n (cette ** hypothèse ** est très importante) À ce moment, n est-il divisé par un nombre premier supérieur à √n?
En fait, c'est impossible.
Si n ÷ m (nombre premier supérieur à √n) = k (entier) n ÷ k = m est vrai, non? Mais compte tenu de la nature de √ m> k (Parce que si m <k, vous pouvez écrire k = m + a n = m * (m + a) = m ^ 2 + m * a et l'égalité est boguée) Même si j'ai supposé qu'il ne serait pas divisé par tous les nombres premiers inférieurs à √n, il serait divisé par un tel k. La proposition 2.2 était censée être considérée dans la gamme des nombres premiers de 1 à n ÷ 2. En fait, c'était bien d'avoir un nombre premier inférieur à 1 ~ √n! Alors implémentons ceci
def number6(n):
li=[2,3]
cnt=2
for i in range(5,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and j**2>=i:#point de changement
cnt+=1
li.append(i)
break
return cnt
C'est assez rapide. Cela devrait suffire pour jouer, et avec cela, seule la connaissance du nombre de nombres premiers peut battre M. Euler (probablement).
Visons un peu plus de vitesse
Cela a été mentionné dans mon manuel de mathématiques du premier cycle du secondaire, mais il existe un moyen de trouver un nombre premier appelé ** Tamis d'Eratostène **. Tout d'abord, écrivez les nombres 2,3,4,5,6, ..., n
Implémentons cela par programme! Est l'idée
Je me demande si ce sera comme suit si je l'écris docilement
def number7(n):
li=[int(x) for x in range(2,n+1)]
pri=[]
for i in range(n):
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
Mais c'est assez lent. Tout ce que vous pensiez ci-dessus prendra vie! Cela correspond à la partie de l'écriture des nombres en premier
li=[int(x) for x in range(2,n+1)]
Partie de. Vous n'êtes pas obligé de l'écrire depuis le début car vous savez que les nombres pairs disparaissent en premier. Faisons cela
def number8(n):
li=[int(x) for x in range(3,n+1,2)]#point de changement
pri=[2]#point de changement
for i in range(n):
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
Cependant, c'est encore assez lent. Parce que Dans la seconde moitié, le tamisage est déjà terminé. Je pense qu'avec n = 100 Effacez les multiples de 3,5,7. En fait, à ce stade, tous les nombres premiers inférieurs à ** 100 sont sortis ** C'est la même chose que l'histoire précédente. ** Un nombre premier inférieur à √n suffit ** Mais l'ordinateur vérifie le tamis jusqu'au dernier nombre premier 97, et tous les nombres de la liste sont des multiples de 11, 13 ou 17, 17 ..., 97? Je suis sûr. Ce processus inutile ralentit. Ajoutons donc un processus qui ** √n suffit **
def number9(n):
li=[int(x) for x in range(3,n+1,2)]
pri=[2]
for i in range(n):
if pri[-1]**2>n: #Voici les changements
pri+=li
break
else:
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
C'est assez rapide! Concurrencons le programme précédent!
Cette fois, nous mesurerons la vitesse uniquement avec le numéro 6 et le numéro 9! Respectez 1000009 d'Euler et calculez 10 fois avec n = 1 000 000 et calculez la moyenne.
number6 :Temps moyen 5.729981923103333
number9 :Temps moyen 3.960706377029419
Le tamis est rapide (le temps varie en fonction des spécifications du PC, il est donc à titre indicatif uniquement)
J'ai essayé de résumer comment trouver le nombre de nombres premiers de base. J'espère que cela aide> <
Sur une note différente, je n'ai pas pu étudier le programme récemment en raison d'un événement universitaire majeur () appelé étude de test. J'aimerais me consacrer à l'amélioration de mes compétences pendant ces vacances d'été, alors j'apprécierais vos conseils et vos encouragements!
Recommended Posts