Python :: Aufgabe #171
1 Lösung
Gaußsche Primzahlendecke
Fortgeschrittener - Python
von hollst
- 07.11.2017 um 12:18 Uhr
Die Gaußsche Primzahlendecke soll als Textilie in den 60er Jahren in den USA ein echter Verkaufsschlager gewesen sein.
Es handelt sich dabei um ein (weißes) Tuch, das entsprechend der Verteilung der Primzahlen in der (komplexen) Gaußschen
Ebene bestickt ist. Genau ein solches Muster wollen auch wir hier mittels Coding erzeugen (Abb. 1).
Während die Sache mit den "normalen" Primzahlen recht einfach zu verstehen ist (Primzahl ist eine Ganzzahl, die nur durch
sich selbst bzw. durch EINS ohne Rest teilbar ist), ist das mit den komplexen Primzahlen schon etwas schwieriger, wir haben
es hier schließlich mit einem Zahlenpaar (Real- und Imaginärteil) zu tun. Besonders interessant ist, das einige "normale"
Primzahlen (z. B. 13 = (3 + 2 * i) * (3 - 2 * i)) keine komplexen Primzahlen sind (was sag ich einige, es sind unendlich viele).
Ohne uns vertiefend mit der Zahlentheorie zu beschäftigen, hier die wesentlichen Voraussetzungen für die Programmierung:
Eine komplexe Integerzahl Z = X + i * Y (X (Realteil), Y (Imaginärteil) Ganzahlen, i * i = -1) heißt Gaußsche Primzahl,
wenn sie eine der drei folgenden Bedingungen erfüllt:
1. Wenn sowohl X als auch Y ungleich 0 sind, dann ist Z eine Gaußsche Primzahl, wenn (X * X + Y * Y) eine "normale" Primzahl ist,
2. ist X = 0, dann ist Z = i * Y Gaußsche Primzahl, wenn Y "normale" Primzahl ist und wenn |Y| = 3 (mod 4) (oder in c#: Math.Abs(Y) % 4 == 3) ist,
3. ist Y = 0, dann ist Z = X Gaußsche Primzahl, wenn X "normale" Primzahl ist und wenn |X| = 3 (mod 4) ist.
Die Programmieraufgabe bestehe nun darin, die Gaußschen Primzahlen für {|X|, |Y|} <= N (z. B. N = 50, Abb. 2 (nur erster Quadrant))
graphisch darzustellen.
Es handelt sich dabei um ein (weißes) Tuch, das entsprechend der Verteilung der Primzahlen in der (komplexen) Gaußschen
Ebene bestickt ist. Genau ein solches Muster wollen auch wir hier mittels Coding erzeugen (Abb. 1).
Während die Sache mit den "normalen" Primzahlen recht einfach zu verstehen ist (Primzahl ist eine Ganzzahl, die nur durch
sich selbst bzw. durch EINS ohne Rest teilbar ist), ist das mit den komplexen Primzahlen schon etwas schwieriger, wir haben
es hier schließlich mit einem Zahlenpaar (Real- und Imaginärteil) zu tun. Besonders interessant ist, das einige "normale"
Primzahlen (z. B. 13 = (3 + 2 * i) * (3 - 2 * i)) keine komplexen Primzahlen sind (was sag ich einige, es sind unendlich viele).
Ohne uns vertiefend mit der Zahlentheorie zu beschäftigen, hier die wesentlichen Voraussetzungen für die Programmierung:
Eine komplexe Integerzahl Z = X + i * Y (X (Realteil), Y (Imaginärteil) Ganzahlen, i * i = -1) heißt Gaußsche Primzahl,
wenn sie eine der drei folgenden Bedingungen erfüllt:
1. Wenn sowohl X als auch Y ungleich 0 sind, dann ist Z eine Gaußsche Primzahl, wenn (X * X + Y * Y) eine "normale" Primzahl ist,
2. ist X = 0, dann ist Z = i * Y Gaußsche Primzahl, wenn Y "normale" Primzahl ist und wenn |Y| = 3 (mod 4) (oder in c#: Math.Abs(Y) % 4 == 3) ist,
3. ist Y = 0, dann ist Z = X Gaußsche Primzahl, wenn X "normale" Primzahl ist und wenn |X| = 3 (mod 4) ist.
Die Programmieraufgabe bestehe nun darin, die Gaußschen Primzahlen für {|X|, |Y|} <= N (z. B. N = 50, Abb. 2 (nur erster Quadrant))
graphisch darzustellen.
Lösungen:
Python-Code
#----------------------------------------------------
# Dateiname: gauß_primdecke.py
# Über eine Liste werden sämtliche komplexen Zahlen {|X|, |Y|} <= N erstellt
# mithilfe paralleler Datenverarbeitung wird geprüft, ob es sich bei dem jeweiligen Paar um eine gaussprime Zahl handelt
# aus der Liste mit den komplexen Zahlen und dem entsprechenden Wahrheitswert wird die Grafik erstellt,exemplarisch für den ersten Quadranten
# da zur Darstellung ein Canvas (Tkinter) verwendet wird, erscheint die Darstellung an der x-Achse gespiegelt
# Python 3.6.1
# Nr. 171 trainyourprogrammer.de
# Mot Sonne 11.11.2017
# Vielen Dank an User hollst!
#----------------------------------------------------
from math import ceil,sqrt
from multiprocessing import Pool
from tkinter import *
def check(tupel):
x,y,wahr=tupel
if x!=0 and y!=0:
z=x**2+y**2
for i in range(2,ceil(sqrt(z))):
if z%i==0:
return (x,y,False)
return (x,y,True)
elif x==0:
z=abs(y)
if z%4==3:
for i in range(2,ceil(sqrt(z))):
if z%i==0:
return (x,y,False)
return (x,y,True)
return (x,y,False)
elif y==0:
z=abs(x)
if z%4==3:
for i in range(2,ceil(sqrt(z))):
if z%i==0:
return (x,y,False)
return (x,y,True)
return (x,y,False)
if __name__=='__main__':
L=[]
#Für andere Werte von N muss das Canvas eventuell angepasst werden!
N=50
for x in range(0,N+1):
for y in range(0,N+1):
L.append((x,y,False))
p=Pool()
m=len(L)
#das dritte Argument von map dient der Effizienz, Pool verwendet automatisch die maximale Anzahl der Prozessoren
results=p.map(check,L,m)
p.close()
p.join()
#Widgets
fenster=Tk()
fenster.title("Gaußsche Primzahlendecke")
c=Canvas(fenster,width=12*N,height=12*N)
c=Canvas(fenster,width=12*N,height=12*N)
c.create_line(N,N,N,11*N,arrow=LAST)
c.create_line(N,N,11*N,N,arrow=LAST)
c.create_text(300,580,text='Gaußsche Primzahlen im ersten Quadranten für Real-und Imaginäranteil kleiner als 50')
c.create_text(4*N,N//2,text='Realanteil')
c.create_text(N//2,4*N,text='Ima-\ngin-\nära-\nnte-\nil')
#Für andere Werte von N eventuell anpassen! Hier wurde der Maßstab N/5 verwendet
for i in range(N+1):
c.create_text(N+10*i,N-5,text=str(i),font=('Arial',5))
for i in range(N+1):
c.create_text(N-5,N+10*i,text=str(i),font=('Arial',5))
c.pack()
for x,y,wahr in results:
if wahr:
c.create_oval(N+10*x-3,N+10*y-3,N+10*x+3,N+y*10+3,fill='red')
#Hier können alternativ andersfarbige Objekte eingefügt werden, vorsicht, das geht manchmal auf die Augen :-P
else:
c.create_rectangle(N+10*x-3,N+10*y-3,N+10*x+3,N+y*10+3,fill='black')
fenster.mainloop()