Vérifiez le nombre de nombres premiers inférieur ou égal à n

Qu'est-ce qu'un nombre premier (le début est une discussion)

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.

Pourquoi les nombres premiers sont importants

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.)

Combien de nombres premiers?

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?

À propos de la distribution des nombres premiers

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 **.

Proposition 1.1 Brisons-le quand même

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

Proposition 1.2 Considérons uniquement les nombres impairs

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? ......

Proposition 1.3 Cotes supplémentaires

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

Proposition 2.1 Divisons par un nombre premier!

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.

Proposition 2.2 Divisons par gamme

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!

Proposition 2.3 Considérer la nature des nombres

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

Proposition 3.1 Tamisage

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

  1. Entourez celui du début ②,3,4,5,6,...,n
  2. Effacez tous les multiples du nombre marqué par 〇 ②, 3,5,7,9,11,...,n
  3. Ignorez 〇 et ajoutez 〇 au premier nombre ②,③,5,7,9,11,...,n
  4. Effacez le multiple du nombre marqué par 〇 C'est un algorithme qui répète cela, et les nombres marqués de 〇 sont des nombres premiers inférieurs ou égaux à 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!

Contrôle de vitesse

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)

la fin

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

Vérifiez le nombre de nombres premiers inférieur ou égal à n
Comment vérifier la version de Django
Commande pour vérifier le nombre total de cœurs physiques / cœurs logiques / mémoire physique du processeur sur Mac
Un moyen simple de vérifier la source des modules Python
Comment connaître le numéro de port du service xinetd
Comment obtenir le nombre de chiffres en Python
Essayez d'estimer le nombre de likes sur Twitter
Discrimination des nombres premiers
Comment spécifier un nombre infini de tolérances dans le contrôle de validation d'argument numérique d'argparse
Comment trouver le nombre optimal de clusters pour les k-moyennes
J'ai fait une fonction pour vérifier le modèle de DCGAN
Essayez d'améliorer la précision de l'estimation du nombre de Twitter
Comment augmenter le nombre d'images de jeux de données d'apprentissage automatique
Commandes et fichiers pour vérifier la version de CentOS Linux
Y a-t-il un secret dans la fréquence des nombres de rapport de circonférence?
10. Compter le nombre de lignes
Obtenez le nombre de chiffres
Calculez le nombre de changements
Comment vérifier la taille de la mémoire d'une variable en Python
Essayez de résoudre le problème N Queen avec SA de PyQUBO
J'ai essayé de créer une liste de nombres premiers avec python
Comment vérifier la taille de la mémoire d'un dictionnaire en Python
[TensorFlow 2] Comment vérifier le contenu de Tensor en mode graphique
La première intelligence artificielle. Comment vérifier la version de Tensorflow installée.
Une commande pour vérifier facilement la vitesse du réseau sur la console
Un script qui renvoie 0, 1 attaché au premier Python prime
Je veux vérifier la position de mon visage avec OpenCV!
J'ai utilisé la commande coupe du monde pour vérifier le résultat de la Coupe du monde.