Eine Primzahl ist eine ganze Zahl, die ** 2 oder mehr beträgt und nur offensichtliche Brüche aufweist. Das Offensichtliche hier ist 1 und ich. Mit anderen Worten, n wird eine Primzahl genannt, wenn es nur 1 und n gibt, in denen n ÷ m eine ganze Zahl für eine ganze Zahl n ist.
Das liegt daran, dass die ** Basis ** eine Primzahl ist, wenn Sie einem Produkt eine Reihe positiver Ganzzahlen geben. Jeder, der Mathematik studiert hat, wird verstehen, wie wichtig die Grundlagen sind. Übrigens, wenn die Operation Summe ist, reicht eine Basis aus (nur 1 kann alle positiven ganzen Zahlen bilden)
(Übrigens, in den alten Tagen, als das Grundkonzept nicht beibehalten wurde, scheinen Primzahlen nicht so wichtig zu sein. Es wurde erkannt, dass es solche Zahlen gibt.)
Dr. Euklidisch hat bewiesen, dass die Anzahl der Primzahlen vor langer Zeit unendlich ist. In einer Zeit, in der es kein Konzept der Unendlichkeit gab, schrieb er in dem Satz: "Wenn die Anzahl der Primzahlen eine Zahl ist, gibt es mehr Primzahlen als diese." Heutzutage gibt es das bequeme Konzept der Unendlichkeit, aber wer war Herr Euklidisch, der das Konzept der Unendlichkeit in den Tagen, als es es noch nicht gab, intuitiv so genau verstand?
Es stellt sich heraus, dass die Gesamtzahl der Primzahlen unendlich ist. Aber wie viele Primzahlen gibt es in Zahlen von 1 bis n? Wurde 1896 mit einem ziemlich schwierigen Problem gelöst. (Jetzt gibt es elementare Beleuchtung, aber es ist nur elementar und es ist ziemlich schwer zu verstehen) Darüber hinaus ist es nur ein "Verhältnis" und die genaue Formel "wie viele" ist (wahrscheinlich) noch unbekannt. Wenn Sie jedoch n spezifisch angeben, können Sie Menschen und Hunde mit enormem Verständnis zählen. Weil Sie nur durch alle Zahlen kleiner oder gleich n dividieren und sicherstellen müssen, dass es nur offensichtliche Brüche gibt. Sie können es tun, wenn Sie Ihr Bestes geben. Und es scheint, dass es im 19. Jahrhundert so etwas wie eine Primzahlentabelle gab. Ich kenne die Obergrenze der Anzahl der Primzahlen an Bord nicht. Es scheint jedoch einige Fehler zu geben, und Dr. Euler hat 1797 den Satz bewiesen, dass ** 1000009 keine Primzahl ** ist. Mit anderen Worten: "Ob n eine Primzahl ist oder nicht, kann theoretisch berechnet werden, wenn Sie Ihr Bestes geben, aber es ist ein Fehler." Dann können Sie berechnen, was stattdessen mit einem Computer zu tun ist.
Dieses Mal ist das Ziel kein Programm, das bestimmt, ob n eine Primzahl ist, sondern ein Programm, das ermittelt, wie viele Primzahlen zwischen ** 1 und n ** liegen.
Die Definition, dass n eine Primzahl ist, ist, dass es nichts gibt, das durch eine ganze Zahl von ** 2 bis n-1 ** teilbar ist. Implementieren Sie es dann programmgesteuert
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
Da der Prozess von 2 nicht gut gelaufen ist, habe ich cnt = 1 im Voraus gesetzt, aber ich denke, dass es so aussehen wird, wenn es gehorsam implementiert wird. Auch das ist überwältigend schneller als Menschen, aber zumindest möchte ich Mr. Eulers 1000009 mit explosiver Geschwindigkeit erreichen. Das ist zu spät. Lassen Sie uns über Verbesserungspläne nachdenken
Wenn Sie überlegen, ob es sich um eine Primzahl handelt, sind andere Zahlen als 2 offensichtlich keine Primzahlen, oder? Wenn ja, lassen Sie es uns ausschließen.
def number2(n):
cnt=1
for i in range(3,n+1,2):#← Nur das hat sich geändert
for j in range(2,i):
if i%j==0:
break
elif i%j!=0 and j==i-1:
cnt+=1
return cnt
Jetzt müssen Sie nur noch über Gewinnchancen nachdenken! Die Anzahl der Berechnungen wurde einfach halbiert! Nur noch eine Sache hier ... Wenn die zu teilende Zahl nur eine ungerade Zahl ist, ist es dann nicht möglich, nur eine ungerade Zahl zu teilen? ......
def number3(n):
cnt=2#Wechselpunkt
for i in range(3,n+1,2):
for j in range(3,i,2):#Wechselpunkt
if i%j==0:
break
elif i%j!=0 and j==i-2:#Wechselpunkt
cnt+=1
return cnt
Damit sind alle zu teilenden Zahlen und die zu teilenden Zahlen bis auf 2 ungerade! Die Anzahl der Berechnungen beträgt einfach das 0,25-fache! Es ist jedoch noch spät. Ich werde wütend auf DI ○. Lassen Sie uns darüber nachdenken, ob es Abfall gibt
Wenn n beispielsweise nicht bei 5 brechen würde, würde es bei 25 brechen? Die Antwort ist nein. Wenn n ÷ 25 = ganze Zahl Es wird n ÷ 5 = 5 * Ganzzahl sein. Mit anderen Worten, es ist Zeitverschwendung, durch 9 zu teilen, obwohl es nicht durch 3 oder durch 15 geteilt wurde, obwohl es nicht durch 3 und 5 geteilt wurde. Mit anderen Worten, ** zum Teilen sind nur Primzahlen erforderlich ** Es macht jedoch keinen Sinn, eine Liste von Primzahlen zu verwenden, wenn Sie eine Primzahl suchen möchten. Lassen Sie uns also selbst eine Liste von Primzahlen erstellen. Bestätigen Sie zuerst die Definition erneut Ich dachte, dass es keine Primzahl gibt, bei der n durch eine Zahl von 2 bis n-1 geteilt wird, um eine ganze Zahl zu werden. Nehmen wir an, dass ** n nicht durch eine Primzahl kleiner als n ** teilbar ist! Die Definition ist für beide gleich, aber wenn Sie sie programmgesteuert schreiben, wird sich viel ändern! Wenn Sie ein Programm mit der Idee schreiben, dass nur eine ungerade Zahl geteilt werden kann
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)
Ich denke, es wird! Es ist viel schneller als am Anfang! Es gibt immer noch offensichtliche Verschwendung.
Sie prüfen derzeit, ob n ÷ Primzahl eine Ganzzahl ist. Was ist der Mindestwert dieser "Ganzzahl"? ...... ** 2 **, richtig? Mit anderen Worten, wenn n 100 oder so ist, müssen Sie es nicht durch 53 teilen ...? Weil offensichtlich 100 ÷ 53 weniger als 2 ist. Dann können Sie damit noch mehr Abfall sparen.
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:#Wechselpunkt
li.append(i)
break #Wechselpunkt
return len(li)
Sie können die Reichweite aber trotzdem reduzieren!
Angenommen, n ist nicht durch alle ** Primzahlen kleiner oder gleich √n teilbar (diese ** alle ** Annahme ist sehr wichtig). Ist n zu diesem Zeitpunkt durch eine Primzahl größer als √n geteilt?
Eigentlich ist es unmöglich.
Wenn n ÷ m (Primzahl größer als √n) = k (ganze Zahl) n ÷ k = m gilt, richtig? Aber unter Berücksichtigung der Natur von √ m> k (Denn wenn m <k ist, können Sie k = m + a schreiben n = m * (m + a) = m ^ 2 + m * a und die Gleichheit ist fehlerhaft) Obwohl ich angenommen habe, dass es nicht durch alle Primzahlen kleiner als √n geteilt wird, würde es durch ein solches k geteilt. Vorschlag 2.2 sollte im Bereich der Primzahlen von 1 bis n ÷ 2 berücksichtigt werden. Eigentlich war es gut, eine Primzahl kleiner als 1 ~ √n zu haben! Dann lassen Sie uns dies implementieren
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:#Wechselpunkt
cnt+=1
li.append(i)
break
return cnt
Das ist ziemlich schnell. Dies sollte zum Spielen ausreichen, und damit kann nur die Kenntnis der Anzahl der Primzahlen (wahrscheinlich) Herrn Euler schlagen.
Lassen Sie uns etwas mehr Geschwindigkeit anstreben
Es wurde in meinem Mathematiklehrbuch der Mittelstufe erwähnt, aber es gibt eine Möglichkeit, eine Primzahl namens ** Eratostenes 'Sieb ** zu finden. Schreiben Sie zuerst die Zahlen 2,3,4,5,6, ..., n
Lassen Sie uns dies programmatisch umsetzen! Ist die Idee
Ich frage mich, ob es so sein wird, wenn ich es gehorsam schreibe
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)
Das ist aber ziemlich langsam. Genau das, was Sie oben gedacht haben, wird zum Leben erweckt! Es entspricht dem Teil, in dem zuerst Zahlen geschrieben werden
li=[int(x) for x in range(2,n+1)]
Teil von. Sie müssen es nicht von Anfang an schreiben, weil Sie wissen, dass gerade Zahlen zuerst verschwinden. Lass uns das machen
def number8(n):
li=[int(x) for x in range(3,n+1,2)]#Wechselpunkt
pri=[2]#Wechselpunkt
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)
Dies ist jedoch immer noch ziemlich langsam. weil In der zweiten Hälfte ist das Sieben bereits beendet. Ich denke mit n = 100 Löschen Sie Vielfache von 3,5,7. Tatsächlich sind zu diesem Zeitpunkt alle Primzahlen unter ** 100 out ** Es ist das gleiche wie in der vorherigen Geschichte. ** Eine Primzahl kleiner als √n ist genug ** Aber der Computer überprüft das Sieb bis zur letzten Primzahl 97, und alle Zahlen in der Liste sind Vielfache von 11, 13 oder 17, 17 ..., 97? Ich bin sicher. Dieser nutzlose Prozess verlangsamt sich. Fügen wir also einen Prozess hinzu, der ** √n ausreicht **
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: #Hier sind die Änderungen
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)
Das geht ziemlich schnell! Lassen Sie uns mit dem vorherigen Programm konkurrieren!
Dieses Mal werden wir die Geschwindigkeit nur mit Nummer 6 und Nummer 9 messen! Respektiere Eulers 1000009, setze n = 1.000.000, berechne 10 mal und berechne den Durchschnitt.
number6 :Durchschnittliche Zeit 5.729981923103333
number9 :Durchschnittliche Zeit 3.960706377029419
Das Sieb ist schnell (die Zeit variiert je nach PC-Spezifikationen, daher dient es nur als Referenz)
Ich habe versucht zusammenzufassen, wie man die Anzahl der Grundprimzahlen findet. Ich hoffe es hilft> <
Aus einem anderen Grund konnte ich das Programm in letzter Zeit aufgrund eines großen Universitätsereignisses () namens Teststudium nicht studieren. Ich möchte mich in diesen Sommerferien der Verbesserung meiner Fähigkeiten widmen, daher würde ich mich über Ihre Anleitung und Ermutigung freuen!
Recommended Posts