Primzahlen

Kapitel aktualisiert am 07.02.2019

In diesem Kapitel behandeln wir das Thema Primzahlen als Teil der Zahlentheorie im Bereich der Algebra. Wir erklären dir, was Primzahlen sind, stellen einige interessante Ergebnisse zu Primzahlen vor, erläutern ihre Anwendung an Beispielen und geben dir Aufgaben zum Lernen mit Lösungen.

Grundlegendes zu Primzahlen

Eine der großen, überraschend schwierig zu beantwortenden Fragen in der Mathematik ist, was es mit Zahlen genau auf sich hat. In gewisser Hinsicht haben Menschen sich Zahlen zwar ausgedacht, trotzdem scheinen sie auch unabhängig vom Menschen zu existieren.

Auch wenn Menschen schon lange wissen, dass es so etwas wie Zahlen gibt, ist die Untersuchung der Eigenschaften von Zahlen auch heute noch nicht vorbei.

Deshalb ist die Zahlentheorie bis heute ein lebendiges mathematisches Feld, denn Zahlen haben immer wieder überraschende Eigenschaften, die man ihnen zuordnen und an ihnen beobachten kann.

Eine der wichtigsten Eigenschaften, die man in den natürlichen Zahlen entdeckt hat, ist, dass es so etwas wie Primzahlen gibt. Da diese Eigenschaft sehr grundlegend ist, wurden Primzahlen auch schon in der Antike entdeckt.

Der Name kommt vom lateinischen primus, das heißt Primzahlen sind übersetzt Zahlen erster Klasse, was ihren besonderen Stellenwert in den natürlichen Zahlen unterstreicht.

Was ist eine Primzahl?

Eine Primzahl lässt sich erst einmal recht einfach definieren.

Definition der Primzahl
Ein Primzahl ist eine ganze Zahl, die größer als 1 ist und sich nur durch 1 und sich selbst teilen lässt.

Das heißt, wenn du eine Zahl vor dir hast, die sich durch irgendetwas teilen lässt, kann sie keine Primzahl sein.

Schauen wir uns einfach mal ein paar Zahlen an und überlegen, ob es sich dabei um Primzahlen handelt:

  • Ist 2 eine Primzahl?
    • 2 ist größer als 1
    • 2 ist nur durch 1 und 2 (sich selber) teilbar
    • → die 2 ist eine Primzahl (die kleinste Primzahl)
  • Ist 5 eine Primzahl?
    • 5 ist größer als 1
    • 5 ist nur durch 1 und 5 teilbar, nicht aber durch 2, 3, und 4
    • → die 5 ist eine Primzahl
  • Ist 8 eine Primzahl?
    • 8 ist größer als 1
    • 8 ist durch 1, 2 und 4 teilbar
    • → die 8 ist keine Primzahl

Für kleine Zahlen ist das zunächst einmal relativ einfach: man kann dann meist einfach im Kopf ausprobieren, ob die Zahl einen Teiler hat.

Bei größeren Zahlen sieht das aber schon ganz anders aus. Fragen wir uns zum Beispiel:

  • Ist 15.485.863 eine Primzahl?
    • 15.485.863 ist größer als 1 … dieser Schritt ist jetzt schon nicht mehr so durchzuführen. Die Antwort ist tatsächlich, dass sich die Zahl nur durch 1 und sich selbst teilen lässt
    • → 15.485.863 ist damit eine Primzahl

Wie du siehst, ist es entsprechend für größere Zahlen nicht mehr ganz so leicht zu sagen, ob sie eine Primzahl sind. Deshalb ist es auch eine Herausforderung für Mathematiker, von immer größeren Zahlen festzustellen, ob sie Primzahlen sind.

Regelmäßig wird mit der Hilfe von Computern die neue größte, bekannte Primzahl gefunden. Der derzeitige Rekord (Stand: 07.02.2019) liegt bei der Zahl \( 2^{82.589.933}−1 \) – eine Zahl mit \(24.862.048\) Stellen.

Aus den grundlegenden Eigenschaften der Primzahlen lässt sich schon ableiten, dass sich keine Primzahl als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, schreiben lässt. Sonst könntest du sie ja durch diese teilen und die Primzahl wäre keine Primzahl mehr.

Primzahlen bis 100.000

Wir haben für dich eine Tabelle mit allen Primzahlen bis 100.000 erstellt, die du dir anschauen und, wenn dir sehr langweilig ist, sogar auswendig lernen kannst. ☺️

          
2357111317192329
31374143475359616771
7379838997101103107109113
127131137139149151157163167173
179181191193197199211223227229
233239241251257263269271277281
283293307311313317331337347349
353359367373379383389397401409
419421431433439443449457461463
467479487491499503509521523541
547557563569571577587593599601
607613617619631641643647653659
661673677683691701709719727733
739743751757761769773787797809
811821823827829839853857859863
877881883887907911919929937941
94795396797197798399199710091013
1019102110311033103910491051106110631069
1087109110931097110311091117112311291151
1153116311711181118711931201121312171223
1229123112371249125912771279128312891291
1297130113031307131913211327136113671373
1381139914091423142714291433143914471451
1453145914711481148314871489149314991511
1523153115431549155315591567157115791583
1597160116071609161316191621162716371657
1663166716691693169716991709172117231733
1741174717531759177717831787178918011811
1823183118471861186718711873187718791889
1901190719131931193319491951197319791987
1993199719992003201120172027202920392053
2063206920812083208720892099211121132129
2131213721412143215321612179220322072213
2221223722392243225122672269227322812287
2293229723092311233323392341234723512357
2371237723812383238923932399241124172423
2437244124472459246724732477250325212531
2539254325492551255725792591259326092617
2621263326472657265926632671267726832687
2689269326992707271127132719272927312741
2749275327672777278927912797280128032819
2833283728432851285728612879288728972903
2909291729272939295329572963296929712999
3001301130193023303730413049306130673079
3083308931093119312131373163316731693181
3187319132033209321732213229325132533257
3259327132993301330733133319332333293331
3343334733593361337133733389339134073413
3433344934573461346334673469349134993511
3517352735293533353935413547355735593571
3581358335933607361336173623363136373643
3659367136733677369136973701370937193727
3733373937613767376937793793379738033821
3823383338473851385338633877388138893907
3911391739193923392939313943394739673989
4001400340074013401940214027404940514057
4073407940914093409941114127412941334139
4153415741594177420142114217421942294231
4241424342534259426142714273428342894297
4327433743394349435743634373439143974409
4421442344414447445144574463448144834493
4507451345174519452345474549456145674583
4591459746034621463746394643464946514657
4663467346794691470347214723472947334751
4759478347874789479347994801481348174831
4861487148774889490349094919493149334937
4943495149574967496949734987499349995003
5009501150215023503950515059507750815087
5099510151075113511951475153516751715179
5189519752095227523152335237526152735279
5281529753035309532353335347535153815387
5393539954075413541754195431543754415443
5449547154775479548355015503550755195521
5527553155575563556955735581559156235639
5641564756515653565756595669568356895693
5701571157175737574157435749577957835791
5801580758135821582758395843584958515857
5861586758695879588158975903592359275939
5953598159876007601160296037604360476053
6067607360796089609161016113612161316133
6143615161636173619761996203621162176221
6229624762576263626962716277628762996301
6311631763236329633763436353635963616367
6373637963896397642164276449645164696473
6481649165216529654765516553656365696571
6577658165996607661966376653665966616673
6679668966916701670367096719673367376761
6763677967816791679368036823682768296833
6841685768636869687168836899690769116917
6947694969596961696769716977698369916997
7001701370197027703970437057706970797103
7109712171277129715171597177718771937207
7211721372197229723772437247725372837297
7307730973217331733373497351736973937411
7417743374517457745974777481748774897499
7507751775237529753775417547754975597561
7573757775837589759176037607762176397643
7649766976737681768776917699770377177723
7727774177537757775977897793781778237829
7841785378677873787778797883790179077919
7927793379377949795179637993800980118017
8039805380598069808180878089809381018111
8117812381478161816781718179819182098219
8221823182338237824382638269827382878291
8293829783118317832983538363836983778387
8389841984238429843184438447846184678501
8513852185278537853985438563857385818597
8599860986238627862986418647866386698677
8681868986938699870787138719873187378741
8747875387618779878388038807881988218831
8837883988498861886388678887889389238929
8933894189518963896989718999900190079011
9013902990419043904990599067909191039109
9127913391379151915791619173918191879199
9203920992219227923992419257927792819283
9293931193199323933793419343934993719377
9391939794039413941994219431943394379439
9461946394679473947994919497951195219533
9539954795519587960196139619962396299631
9643964996619677967996899697971997219733
9739974397499767976997819787979198039811
9817982998339839985198579859987198839887
99019907992399299931994199499967997310007
10009100371003910061100671006910079100911009310099
10103101111013310139101411015110159101631016910177
10181101931021110223102431024710253102591026710271
10273102891030110303103131032110331103331033710343
10357103691039110399104271042910433104531045710459
10463104771048710499105011051310529105311055910567
10589105971060110607106131062710631106391065110657
10663106671068710691107091071110723107291073310739
10753107711078110789107991083110837108471085310859
10861108671088310889108911090310909109371093910949
10957109731097910987109931100311027110471105711059
11069110711108311087110931111311117111191113111149
11159111611117111173111771119711213112391124311251
11257112611127311279112871129911311113171132111329
11351113531136911383113931139911411114231143711443
11447114671147111483114891149111497115031151911527
11549115511157911587115931159711617116211163311657
11677116811168911699117011171711719117311174311777
11779117831178911801118071181311821118271183111833
11839118631186711887118971190311909119231192711933
11939119411195311959119691197111981119871200712011
12037120411204312049120711207312097121011210712109
12113121191214312149121571216112163121971220312211
12227122391224112251122531226312269122771228112289
12301123231232912343123471237312377123791239112401
12409124131242112433124371245112457124731247912487
12491124971250312511125171252712539125411254712553
12569125771258312589126011261112613126191263712641
12647126531265912671126891269712703127131272112739
12743127571276312781127911279912809128211282312829
12841128531288912893128991290712911129171291912923
12941129531295912967129731297912983130011300313007
13009130331303713043130491306313093130991310313109
13121131271314713151131591316313171131771318313187
13217132191322913241132491325913267132911329713309
13313133271333113337133391336713381133971339913411
13417134211344113451134571346313469134771348713499
13513135231353713553135671357713591135971361313619
13627136331364913669136791368113687136911369313697
13709137111372113723137291375113757137591376313781
13789137991380713829138311384113859138731387713879
13883139011390313907139131392113931139331396313967
13997139991400914011140291403314051140571407114081
14083140871410714143141491415314159141731417714197
14207142211424314249142511428114293143031432114323
14327143411434714369143871438914401144071441114419
14423144311443714447144491446114479144891450314519
14533145371454314549145511455714561145631459114593
14621146271462914633146391465314657146691468314699
14713147171472314731147371474114747147531475914767
14771147791478314797148131482114827148311484314851
14867148691487914887148911489714923149291493914947
14951149571496914983150131501715031150531506115073
15077150831509115101151071512115131151371513915149
15161151731518715193151991521715227152331524115259
15263152691527115277152871528915299153071531315319
15329153311534915359153611537315377153831539115401
15413154271543915443154511546115467154731549315497
15511155271554115551155591556915581155831560115607
15619156291564115643156471564915661156671567115679
15683157271573115733157371573915749157611576715773
15787157911579715803158091581715823158591587715881
15887158891590115907159131591915923159371595915971
15973159911600116007160331605716061160631606716069
16073160871609116097161031611116127161391614116183
16187161891619316217162231622916231162491625316267
16273163011631916333163391634916361163631636916381
16411164171642116427164331644716451164531647716481
16487164931651916529165471655316561165671657316603
16607166191663116633166491665116657166611667316691
16693166991670316729167411674716759167631678716811
16823168291683116843168711687916883168891690116903
16921169271693116937169431696316979169811698716993
17011170211702717029170331704117047170531707717093
17099171071711717123171371715917167171831718917191
17203172071720917231172391725717291172931729917317
17321173271733317341173511735917377173831738717389
17393174011741717419174311744317449174671747117477
17483174891749117497175091751917539175511756917573
17579175811759717599176091762317627176571765917669
17681176831770717713177291773717747177491776117783
17789177911780717827178371783917851178631788117891
17903179091791117921179231792917939179571795917971
17977179811798717989180131804118043180471804918059
18061180771808918097181191812118127181311813318143
18149181691818118191181991821118217182231822918233
18251182531825718269182871828918301183071831118313
18329183411835318367183711837918397184011841318427
18433184391844318451184571846118481184931850318517
18521185231853918541185531858318587185931861718637
18661186711867918691187011871318719187311874318749
18757187731878718793187971880318839188591886918899
18911189131891718919189471895918973189791900119009
19013190311903719051190691907319079190811908719121
19139191411915719163191811918319207192111921319219
19231192371924919259192671927319289193011930919319
19333193731937919381193871939119403194171942119423
19427194291943319441194471945719463194691947119477
19483194891950119507195311954119543195531955919571
19577195831959719603196091966119681196871969719699
19709197171972719739197511975319759197631977719793
19801198131981919841198431985319861198671988919891
19913199191992719937199491996119963199731997919991
19993199972001120021200232002920047200512006320071
20089201012010720113201172012320129201432014720149
20161201732017720183202012021920231202332024920261
20269202872029720323203272033320341203472035320357
20359203692038920393203992040720411204312044120443
20477204792048320507205092052120533205432054920551
20563205932059920611206272063920641206632068120693
20707207172071920731207432074720749207532075920771
20773207892080720809208492085720873208792088720897
20899209032092120929209392094720959209632098120983
21001210112101321017210192102321031210592106121067
21089211012110721121211392114321149211572116321169
21179211872119121193212112122121227212472126921277
21283213132131721319213232134121347213772137921383
21391213972140121407214192143321467214812148721491
21493214992150321517215212152321529215572155921563
21569215772158721589215992160121611216132161721647
21649216612167321683217012171321727217372173921751
21757217672177321787217992180321817218212183921841
21851218592186321871218812189321911219292193721943
21961219772199121997220032201322027220312203722039
22051220632206722073220792209122093221092211122123
22129221332214722153221572215922171221892219322229
22247222592227122273222772227922283222912230322307
22343223492236722369223812239122397224092243322441
22447224532246922481224832250122511225312254122543
22549225672257122573226132261922621226372263922643
22651226692267922691226972269922709227172272122727
22739227412275122769227772278322787228072281122817
22853228592286122871228772290122907229212293722943
22961229632297322993230032301123017230212302723029
23039230412305323057230592306323071230812308723099
23117231312314323159231672317323189231972320123203
23209232272325123269232792329123293232972331123321
23327233332333923357233692337123399234172343123447
23459234732349723509235312353723539235492355723561
23563235672358123593235992360323609236232362723629
23633236632366923671236772368723689237192374123743
23747237532376123767237732378923801238132381923827
23831238332385723869238732387923887238932389923909
23911239172392923957239712397723981239932400124007
24019240232402924043240492406124071240772408324091
24097241032410724109241132412124133241372415124169
24179241812419724203242232422924239242472425124281
24317243292433724359243712437324379243912440724413
24419244212443924443244692447324481244992450924517
24527245332454724551245712459324611246232463124659
24671246772468324691246972470924733247492476324767
24781247932479924809248212484124847248512485924877
24889249072491724919249232494324953249672497124977
24979249892501325031250332503725057250732508725097
25111251172512125127251472515325163251692517125183
25189252192522925237252432524725253252612530125303
25307253092532125339253432534925357253672537325391
25409254112542325439254472545325457254632546925471
25523255372554125561255772557925583255892560125603
25609256212563325639256432565725667256732567925693
25703257172573325741257472575925763257712579325799
25801258192584125847258492586725873258892590325913
25919259312593325939259432595125969259812599725999
26003260172602126029260412605326083260992610726111
26113261192614126153261612617126177261832618926203
26209262272623726249262512626126263262672629326297
26309263172632126339263472635726371263872639326399
26407264172642326431264372644926459264792648926497
26501265132653926557265612657326591265972662726633
26641266472666926681266832668726693266992670126711
26713267172672326729267312673726759267772678326801
26813268212683326839268492686126863268792688126891
26893269032692126927269472695126953269592698126987
26993270112701727031270432705927061270672707327077
27091271032710727109271272714327179271912719727211
27239272412725327259272712727727281272832729927329
27337273612736727397274072740927427274312743727449
27457274792748127487275092752727529275392754127551
27581275832761127617276312764727653276732768927691
27697277012773327737277392774327749277512776327767
27773277792779127793277992780327809278172782327827
27847278512788327893279012791727919279412794327947
27953279612796727983279972800128019280272803128051
28057280692808128087280972809928109281112812328151
28163281812818328201282112821928229282772827928283
28289282972830728309283192834928351283872839328403
28409284112842928433284392844728463284772849328499
28513285172853728541285472854928559285712857328579
28591285972860328607286192862128627286312864328649
28657286612866328669286872869728703287112872328729
28751287532875928771287892879328807288132881728837
28843288592886728871288792890128909289212892728933
28949289612897929009290172902129023290272903329059
29063290772910129123291292913129137291472915329167
29173291792919129201292072920929221292312924329251
29269292872929729303293112932729333293392934729363
29383293872938929399294012941129423294292943729443
29453294732948329501295272953129537295672956929573
29581295872959929611296292963329641296632966929671
29683297172972329741297532975929761297892980329819
29833298372985129863298672987329879298812991729921
29927299472995929983299893001130013300293004730059
30071300893009130097301033010930113301193013330137
30139301613016930181301873019730203302113022330241
30253302593026930271302933030730313303193032330341
30347303673038930391304033042730431304493046730469
30491304933049730509305173052930539305533055730559
30577305933063130637306433064930661306713067730689
30697307033070730713307273075730763307733078130803
30809308173082930839308413085130853308593086930871
30881308933091130931309373094130949309713097730983
31013310193103331039310513106331069310793108131091
31121311233113931147311513115331159311773118131183
31189311933121931223312313123731247312493125331259
31267312713127731307313193132131327313333133731357
31379313873139131393313973146931477314813148931511
31513315173153131541315433154731567315733158331601
31607316273164331649316573166331667316873169931721
31723317273172931741317513176931771317933179931817
31847318493185931873318833189131907319573196331973
31981319913200332009320273202932051320573205932063
32069320773208332089320993211732119321413214332159
32173321833218932191322033221332233322373225132257
32261322973229932303323093232132323323273234132353
32359323633236932371323773238132401324113241332423
32429324413244332467324793249132497325033250732531
32533325373256132563325693257332579325873260332609
32611326213263332647326533268732693327073271332717
32719327493277132779327833278932797328013280332831
32833328393284332869328873290932911329173293332939
32941329573296932971329833298732993329993301333023
33029330373304933053330713307333083330913310733113
33119331493315133161331793318133191331993320333211
33223332473328733289333013331133317333293333133343
33347333493335333359333773339133403334093341333427
33457334613346933479334873349333503335213352933533
33547335633356933577335813358733589335993360133613
33617336193362333629336373364133647336793370333713
33721337393374933751337573376733769337733379133797
33809338113382733829338513385733863338713388933893
33911339233393133937339413396133967339973401934031
34033340393405734061341233412734129341413414734157
34159341713418334211342133421734231342533425934261
34267342733428334297343013430334313343193432734337
34351343613436734369343813440334421344293443934457
34469344713448334487344993450134511345133451934537
34543345493458334589345913460334607346133463134649
34651346673467334679346873469334703347213472934739
34747347573475934763347813480734819348413484334847
34849348713487734883348973491334919349393494934961
34963349813502335027350513505335059350693508135083
35089350993510735111351173512935141351493515335159
35171352013522135227352513525735267352793528135291
35311353173532335327353393535335363353813539335401
35407354193542335437354473544935461354913550735509
35521355273553135533355373554335569355733559135593
35597356033561735671356773572935731357473575335759
35771357973580135803358093583135837358393585135863
35869358793589735899359113592335933359513596335969
35977359833599335999360073601136013360173603736061
36067360733608336097361073610936131361373615136161
36187361913620936217362293624136251362633626936277
36293362993630736313363193634136343363533637336383
36389364333645136457364673646936473364793649336497
36523365273652936541365513655936563365713658336587
36599366073662936637366433665336671366773668336691
36697367093671336721367393674936761367673677936781
36787367913679336809368213683336847368573687136877
36887368993690136913369193692336929369313694336947
36973369793699737003370133701937021370393704937057
37061370873709737117371233713937159371713718137189
37199372013721737223372433725337273372773730737309
37313373213733737339373573736137363373693737937397
37409374233744137447374633748337489374933750137507
37511375173752937537375473754937561375673757137573
37579375893759137607376193763337643376493765737663
37691376933769937717377473778137783377993781137813
37831378473785337861378713787937889378973790737951
37957379633796737987379913799337997380113803938047
38053380693808338113381193814938153381673817738183
38189381973820138219382313823738239382613827338281
38287382993830338317383213832738329383333835138371
38377383933843138447384493845338459384613850138543
38557385613856738569385933860338609386113862938639
38651386533866938671386773869338699387073871138713
38723387293873738747387493876738783387913880338821
38833388393885138861388673887338891389033891738921
38923389333895338959389713897738993390193902339041
39043390473907939089390973910339107391133911939133
39139391573916139163391813919139199392093921739227
39229392333923939241392513929339301393133931739323
39341393433935939367393713937339383393973940939419
39439394433945139461394993950339509395113952139541
39551395633956939581396073961939623396313965939667
39671396793970339709397193972739733397493976139769
39779397913979939821398273982939839398413984739857
39863398693987739883398873990139929399373995339971
39979399833998940009400134003140037400394006340087
40093400994011140123401274012940151401534016340169
40177401894019340213402314023740241402534027740283
40289403434035140357403614038740423404274042940433
40459404714048340487404934049940507405194052940531
40543405594057740583405914059740609406274063740639
40693406974069940709407394075140759407634077140787
40801408134081940823408294084140847408494085340867
40879408834089740903409274093340939409494096140973
40993410114101741023410394104741051410574107741081
41113411174113141141411434114941161411774117941183
41189412014120341213412214122741231412334124341257
41263412694128141299413334134141351413574138141387
41389413994141141413414434145341467414794149141507
41513415194152141539415434154941579415934159741603
41609416114161741621416274164141647416514165941669
41681416874171941729417374175941761417714177741801
41809418134184341849418514186341879418874189341897
41903419114192741941419474195341957419594196941981
41983419994201342017420194202342043420614207142073
42083420894210142131421394215742169421794218142187
42193421974220942221422234222742239422574228142283
42293422994230742323423314233742349423594237342379
42391423974240342407424094243342437424434245142457
42461424634246742473424874249142499425094253342557
42569425714257742589426114264142643426494266742677
42683426894269742701427034270942719427274273742743
42751427674277342787427934279742821428294283942841
42853428594286342899429014292342929429374294342953
42961429674297942989430034301343019430374304943051
43063430674309343103431174313343151431594317743189
43201432074322343237432614327143283432914331343319
43321433314339143397433994340343411434274344143451
43457434814348743499435174354143543435734357743579
43591435974360743609436134362743633436494365143661
43669436914371143717437214375343759437774378143783
43787437894379343801438534386743889438914391343933
43943439514396143963439694397343987439914399744017
44021440274402944041440534405944071440874408944101
44111441194412344129441314415944171441794418944201
44203442074422144249442574426344267442694427344279
44281442934435144357443714438144383443894441744449
44453444834449144497445014450744519445314453344537
44543445494456344579445874461744621446234463344641
44647446514465744683446874469944701447114472944741
44753447714477344777447894479744809448194483944843
44851448674487944887448934490944917449274493944953
44959449634497144983449874500745013450534506145077
45083451194512145127451314513745139451614517945181
45191451974523345247452594526345281452894529345307
45317453194532945337453414534345361453774538945403
45413454274543345439454814549145497455034552345533
45541455534555745569455874558945599456134563145641
45659456674567345677456914569745707457374575145757
45763457674577945817458214582345827458334584145853
45863458694588745893459434594945953459594597145979
45989460214602746049460514606146073460914609346099
46103461334614146147461534617146181461834618746199
46219462294623746261462714627346279463014630746309
46327463374634946351463814639946411464394644146447
46451464574647146477464894649946507465114652346549
46559465674657346589465914660146619466334663946643
46649466634667946681466874669146703467234672746747
46751467574676946771468074681146817468194682946831
46853468614686746877468894690146919469334695746993
46997470174704147051470574705947087470934711147119
47123471294713747143471474714947161471894720747221
47237472514726947279472874729347297473034730947317
47339473514735347363473814738747389474074741747419
47431474414745947491474974750147507475134752147527
47533475434756347569475814759147599476094762347629
47639476534765747659476814769947701477114771347717
47737477414774347777477794779147797478074780947819
47837478434785747869478814790347911479174793347939
47947479514796347969479774798148017480234802948049
48073480794809148109481194812148131481574816348179
48187481934819748221482394824748259482714828148299
48311483134833748341483534837148383483974840748409
48413484374844948463484734847948481484874849148497
48523485274853348539485414856348571485894859348611
48619486234864748649486614867348677486794873148733
48751487574876148767487794878148787487994880948817
48821488234884748857488594886948871488834888948907
48947489534897348989489914900349009490194903149033
49037490434905749069490814910349109491174912149123
49139491574916949171491774919349199492014920749211
49223492534926149277492794929749307493314933349339
49363493674936949391493934940949411494174942949433
49451494594946349477494814949949523495294953149537
49547495494955949597496034961349627496334963949663
49667496694968149697497114972749739497414974749757
49783497874978949801498074981149823498314984349853
49871498774989149919499214992749937499394994349957
49991499934999950021500235003350047500515005350069
50077500875009350101501115011950123501295013150147
50153501595017750207502215022750231502615026350273
50287502915031150321503295033350341503595036350377
50383503875041150417504235044150459504615049750503
50513505275053950543505495055150581505875059150593
50599506275064750651506715068350707507235074150753
50767507735077750789508215083350839508495085750867
50873508915089350909509235092950951509575096950971
50989509935100151031510435104751059510615107151109
51131511335113751151511575116951193511975119951203
51217512295123951241512575126351283512875130751329
51341513435134751349513615138351407514135141951421
51427514315143751439514495146151473514795148151487
51503515115151751521515395155151563515775158151593
51599516075161351631516375164751659516735167951683
51691517135171951721517495176751769517875179751803
51817518275182951839518535185951869518715189351899
51907519135192951941519495197151973519775199152009
52021520275205152057520675206952081521035212152127
52147521535216352177521815218352189522015222352237
52249522535225952267522895229152301523135232152361
52363523695237952387523915243352453524575248952501
52511525175252952541525435255352561525675257152579
52583526095262752631526395266752673526915269752709
52711527215272752733527475275752769527835280752813
52817528375285952861528795288352889529015290352919
52937529515295752963529675297352981529995300353017
53047530515306953077530875308953093531015311353117
53129531475314953161531715317353189531975320153231
53233532395326753269532795328153299533095332353327
53353533595337753381534015340753411534195343753441
53453534795350353507535275354953551535695359153593
53597536095361153617536235362953633536395365353657
53681536935369953717537195373153759537735377753783
53791538135381953831538495385753861538815388753891
53897538995391753923539275393953951539595398753993
54001540115401354037540495405954083540915410154121
54133541395415154163541675418154193542175425154269
54277542875429354311543195432354331543475436154367
54371543775440154403544095441354419544215443754443
54449544695449354497544995450354517545215453954541
54547545595456354577545815458354601546175462354629
54631546475466754673546795470954713547215472754751
54767547735477954787547995482954833548515486954877
54881549075491754919549415494954959549735497954983
55001550095502155049550515505755061550735507955103
55109551175512755147551635517155201552075521355217
55219552295524355249552595529155313553315533355337
55339553435535155373553815539955411554395544155457
55469554875550155511555295554155547555795558955603
55609556195562155631556335563955661556635566755673
55681556915569755711557175572155733557635578755793
55799558075581355817558195582355829558375584355849
55871558895589755901559035592155927559315593355949
55967559875599756003560095603956041560535608156087
56093560995610156113561235613156149561675617156179
56197562075620956237562395624956263562675626956299
56311563335635956369563775638356393564015641756431
56437564435645356467564735647756479564895650156503
56509565195652756531565335654356569565915659756599
56611566295663356659566635667156681566875670156711
56713567315673756747567675677356779567835680756809
56813568215682756843568575687356891568935689756909
56911569215692356929569415695156957569635698356989
56993569995703757041570475705957073570775708957097
57107571195713157139571435714957163571735717957191
57193572035722157223572415725157259572695727157283
57287573015732957331573475734957367573735738357389
57397574135742757457574675748757493575035752757529
57557575595757157587575935760157637576415764957653
57667576795768957697577095771357719577275773157737
57751577735778157787577915779357803578095782957839
57847578535785957881578995790157917579235794357947
57973579775799158013580275803158043580495805758061
58067580735809958109581115812958147581515815358169
58171581895819358199582075821158217582295823158237
58243582715830958313583215833758363583675836958379
58391583935840358411584175842758439584415845158453
58477584815851158537585435854958567585735857958601
58603586135863158657586615867958687586935869958711
58727587335874158757587635877158787587895883158889
58897589015890758909589135892158937589435896358967
58979589915899759009590115902159023590295905159053
59063590695907759083590935910759113591195912359141
59149591595916759183591975920759209592195922159233
59239592435926359273592815933359341593515935759359
59369593775938759393593995940759417594195944159443
59447594535946759471594735949759509595135953959557
59561595675958159611596175962159627596295965159659
59663596695967159693596995970759723597295974359747
59753597715977959791597975980959833598635987959887
59921599295995159957599715998159999600136001760029
60037600416007760083600896009160101601036010760127
60133601396014960161601676016960209602176022360251
60257602596027160289602936031760331603376034360353
60373603836039760413604276044360449604576049360497
60509605216052760539605896060160607606116061760623
60631606376064760649606596066160679606896070360719
60727607336073760757607616076360773607796079360811
60821608596086960887608896089960901609136091760919
60923609376094360953609616100161007610276103161043
61051610576109161099611216112961141611516115361169
61211612236123161253612616128361291612976133161333
61339613436135761363613796138161403614096141761441
61463614696147161483614876149361507615116151961543
61547615536155961561615836160361609616136162761631
61637616436165161657616676167361681616876170361717
61723617296175161757617816181361819618376184361861
61871618796190961927619336194961961619676197961981
61987619916200362011620176203962047620536205762071
62081620996211962129621316213762141621436217162189
62191622016220762213622196223362273622976229962303
62311623236232762347623516238362401624176242362459
62467624736247762483624976250162507625336253962549
62563625816259162597626036261762627626336263962653
62659626836268762701627236273162743627536276162773
62791628016281962827628516286162869628736289762903
62921629276292962939629696297162981629836298762989
63029630316305963067630736307963097631036311363127
63131631496317963197631996321163241632476327763281
63299633116331363317633316333763347633536336163367
63377633896339163397634096341963421634396344363463
63467634736348763493634996352163527635336354163559
63577635876358963599636016360763611636176362963647
63649636596366763671636896369163697637036370963719
63727637376374363761637736378163793637996380363809
63823638396384163853638576386363901639076391363929
63949639776399764007640136401964033640376406364067
64081640916410964123641516415364157641716418764189
64217642236423164237642716427964283643016430364319
64327643336437364381643996440364433644396445164453
64483644896449964513645536456764577645796459164601
64609646136462164627646336466164663646676467964693
64709647176474764763647816478364793648116481764849
64853648716487764879648916490164919649216492764937
64951649696499765003650116502765029650336505365063
65071650896509965101651116511965123651296514165147
65167651716517365179651836520365213652396525765267
65269652876529365309653236532765353653576537165381
65393654076541365419654236543765447654496547965497
65519655216553765539655436555165557655636557965581
65587655996560965617656296563365647656516565765677
65687656996570165707657136571765719657296573165761
65777657896580965827658316583765839658436585165867
65881658996592165927659296595165957659636598165983
65993660296603766041660476606766071660836608966103
66107661096613766161661696617366179661916622166239
66271662936630166337663436634766359663616637366377
66383664036641366431664496645766463664676649166499
66509665236652966533665416655366569665716658766593
66601666176662966643666536668366697667016671366721
66733667396674966751667636679166797668096682166841
66851668536686366877668836688966919669236693166943
66947669496695966973669776700367021670336704367049
67057670616707367079671036712167129671396714167153
67157671696718167187671896721167213672176721967231
67247672616727167273672896730767339673436734967369
67391673996740967411674216742767429674336744767453
67477674816748967493674996751167523675316753767547
67559675676757767579675896760167607676196763167651
67679676996770967723677336774167751677576775967763
67777677836778967801678076781967829678436785367867
67883678916790167927679316793367939679436795767961
67967679796798767993680236804168053680596807168087
68099681116811368141681476816168171682076820968213
68219682276823968261682796828168311683296835168371
68389683996843768443684476844968473684776848368489
68491685016850768521685316853968543685676858168597
68611686336863968659686696868368687686996871168713
68729687376874368749687676877168777687916881368819
68821688636887968881688916889768899689036890968917
68927689476896368993690016901169019690296903169061
69067690736910969119691276914369149691516916369191
69193691976920369221692336923969247692576925969263
69313693176933769341693716937969383693896940169403
69427694316943969457694636946769473694816949169493
69497694996953969557695936962369653696616967769691
69697697096973769739697616976369767697796980969821
69827698296983369847698576985969877698996991169929
69931699416995969991699977000170003700097001970039
70051700617006770079700997011170117701217012370139
70141701577016370177701817018370199702017020770223
70229702377024170249702717028970297703097031370321
70327703517037370379703817039370423704297043970451
70457704597048170487704897050170507705297053770549
70571705737058370589706077061970621706277063970657
70663706677068770709707177072970753707697078370793
70823708417084370849708537086770877708797089170901
70913709197092170937709497095170957709697097970981
70991709977099971011710237103971059710697108171089
71119711297114371147711537116171167711717119171209
71233712377124971257712617126371287712937131771327
71329713337133971341713477135371359713637138771389
71399714117141371419714297143771443714537147171473
71479714837150371527715377154971551715637156971593
71597716337164771663716717169371699717077171171713
71719717417176171777717897180771809718217183771843
71849718617186771879718817188771899719097191771933
71941719477196371971719837198771993719997201972031
72043720477205372073720777208972091721017210372109
72139721617216772169721737221172221722237222772229
72251722537226972271722777228772307723137233772341
72353723677237972383724217243172461724677246972481
72493724977250372533725477255172559725777261372617
72623726437264772649726617267172673726797268972701
72707727197272772733727397276372767727977281772823
72859728697287172883728897289372901729077291172923
72931729377294972953729597297372977729977300973013
73019730377303973043730617306373079730917312173127
73133731417318173189732377324373259732777329173303
73309733277333173351733617336373369733797338773417
73421734337345373459734717347773483735177352373529
73547735537356173571735837358973597736077360973613
73637736437365173673736797368173693736997370973721
73727737517375773771737837381973823738477384973859
73867738777388373897739077393973943739517396173973
73999740177402174027740477405174071740777409374099
74101741317414374149741597416174167741777418974197
74201742037420974219742317425774279742877429374297
74311743177432374353743577436374377743817438374411
74413744197444174449744537447174489745077450974521
74527745317455174561745677457374587745977460974611
74623746537468774699747077471374717747197472974731
74747747597476174771747797479774821748277483174843
74857748617486974873748877489174897749037492374929
74933749417495975011750137501775029750377504175079
75083751097513375149751617516775169751817519375209
75211752177522375227752397525375269752777528975307
75323753297533775347753537536775377753897539175401
75403754077543175437754797550375511755217552775533
75539755417555375557755717557775583756117561775619
75629756417565375659756797568375689757037570775709
75721757317574375767757737578175787757937579775821
75833758537586975883759137593175937759417596775979
75983759897599175997760017600376031760397607976081
76091760997610376123761297614776157761597616376207
76213762317624376249762537625976261762837628976303
76333763437636776369763797638776403764217642376441
76463764717648176487764937650776511765197653776541
76543765617657976597766037660776631766497665176667
76673766797669776717767337675376757767717677776781
76801768197682976831768377684776871768737688376907
76913769197694376949769617696376991770037701777023
77029770417704777069770817709377101771377714177153
77167771717719177201772137723777239772437724977261
77263772677726977279772917731777323773397734777351
77359773697737777383774177741977431774477747177477
77479774897749177509775137752177527775437754977551
77557775637756977573775877759177611776177762177641
77647776597768177687776897769977711777137771977723
77731777437774777761777737778377797778017781377839
77849778637786777893778997792977933779517796977977
77983779997800778017780317804178049780597807978101
78121781377813978157781637816778173781797819178193
78203782297823378241782597827778283783017830778311
78317783417834778367784017842778437784397846778479
78487784977850978511785177853978541785537856978571
78577785837859378607786237864378649786537869178697
78707787137872178737787797878178787787917879778803
78809788237883978853788577887778887788897889378901
78919789297894178977789797898979031790397904379063
79087791037911179133791397914779151791537915979181
79187791937920179229792317924179259792737927979283
79301793097931979333793377934979357793677937979393
79397793997941179423794277943379451794817949379531
79537795497955979561795797958979601796097961379621
79627796317963379657796697968779691796937969779699
79757797697977779801798117981379817798237982979841
79843798477986179867798737988979901799037990779939
79943799677997379979799877999779999800218003980051
80071800778010780111801418014780149801538016780173
80177801918020780209802218023180233802398025180263
80273802798028780309803178032980341803478036380369
80387804078042980447804498047180473804898049180513
80527805378055780567805998060380611806218062780629
80651806578066980671806778068180683806878070180713
80737807478074980761807778077980783807898080380809
80819808318083380849808638089780909809118091780923
80929809338095380963809898100181013810178101981023
81031810418104381047810498107181077810838109781101
81119811318115781163811738118181197811998120381223
81233812398128181283812938129981307813318134381349
81353813598137181373814018140981421814398145781463
81509815178152781533815478155181553815598156381569
81611816198162981637816478164981667816718167781689
81701817038170781727817378174981761817698177381799
81817818398184781853818698188381899819018191981929
81931819378194381953819678197181973820038200782009
82013820218203182037820398205182067820738212982139
82141821538216382171821838218982193822078221782219
82223822318223782241822618226782279823018230782339
82349823518236182373823878239382421824578246382469
82471824838248782493824998250782529825318254982559
82561825678257182591826018260982613826198263382651
82657826998272182723827278272982757827598276382781
82787827938279982811828138283782847828838288982891
82903829138293982963829818299783003830098302383047
83059830638307183077830898309383101831178313783177
83203832078321983221832278323183233832438325783267
83269832738329983311833398334183357833838338983399
83401834078341783423834318343783443834498345983471
83477834978353783557835618356383579835918359783609
83617836218363983641836538366383689837018371783719
83737837618377383777837918381383833838438385783869
83873838918390383911839218393383939839698398383987
84011840178404784053840598406184067840898412184127
84131841378414384163841798418184191841998421184221
84223842298423984247842638429984307843138431784319
84347843498437784389843918440184407844218443184437
84443844498445784463844678448184499845038450984521
84523845338455184559845898462984631846498465384659
84673846918469784701847138471984731847378475184761
84787847938480984811848278485784859848698487184913
84919849478496184967849778497984991850098502185027
85037850498506185081850878509185093851038510985121
85133851478515985193851998520185213852238522985237
85243852478525985297853038531385331853338536185363
85369853818541185427854298543985447854518545385469
85487855138551785523855318554985571855778559785601
85607856198562185627856398564385661856678566985691
85703857118571785733857518578185793858178581985829
85831858378584385847858538588985903859098593185933
85991859998601186017860278602986069860778608386111
86113861178613186137861438616186171861798618386197
86201862098623986243862498625786263862698628786291
86293862978631186323863418635186353863578636986371
86381863898639986413864238644186453864618646786477
86491865018650986531865338653986561865738657986587
86599866278662986677866898669386711867198672986743
86753867678677186783868138683786843868518685786861
86869869238692786929869398695186959869698698186993
87011870138703787041870498707187083871038710787119
87121871338714987151871798718187187872118722187223
87251872538725787277872818729387299873138731787323
87337873598738387403874078742187427874338744387473
87481874918750987511875178752387539875418754787553
87557875598758387587875898761387623876298763187641
87643876498767187679876838769187697877018771987721
87739877438775187767877938779787803878118783387853
87869878778788187887879118791787931879438795987961
87973879778799188001880038800788019880378806988079
88093881178812988169881778821188223882378824188259
88261882898830188321883278833788339883798839788411
88423884278846388469884718849388499885138852388547
88589885918860788609886438865188657886618866388667
88681887218872988741887478877188789887938879988801
88807888118881388817888198884388853888618886788873
88883888978890388919889378895188969889938899789003
89009890178902189041890518905789069890718908389087
89101891078911389119891238913789153891898920389209
89213892278923189237892618926989273892938930389317
89329893638937189381893878939389399894138941789431
89443894498945989477894918950189513895198952189527
89533895618956389567895918959789599896038961189627
89633896538965789659896698967189681896898975389759
89767897798978389797898098981989821898338983989849
89867898918989789899899098991789923899398995989963
89977899838998990001900079001190017900199002390031
90053900599006790071900739008990107901219012790149
90163901739018790191901979019990203902179022790239
90247902639027190281902899031390353903599037190373
90379903979040190403904079043790439904699047390481
90499905119052390527905299053390547905839059990617
90619906319064190647906599067790679906979070390709
90731907499078790793908039082190823908339084190847
90863908879090190907909119091790931909479097190977
90989909979100991019910339107991081910979109991121
91127911299113991141911519115391159911639118391193
91199912299123791243912499125391283912919129791303
91309913319136791369913739138191387913939139791411
91423914339145391457914599146391493914999151391529
91541915719157391577915839159191621916319163991673
91691917039171191733917539175791771917819180191807
91811918139182391837918419186791873919099192191939
91943919519195791961919679196991997920039200992033
92041920519207792083921079211192119921439215392173
92177921799218992203922199222192227922339223792243
92251922699229792311923179233392347923539235792363
92369923779238192383923879239992401924139241992431
92459924619246792479924899250392507925519255792567
92569925819259392623926279263992641926479265792669
92671926819268392693926999270792717927239273792753
92761927679277992789927919280192809928219283192849
92857928619286392867928939289992921929279294192951
92957929599298792993930019304793053930599307793083
93089930979310393113931319313393139931519316993179
93187931999322993239932419325193253932579326393281
93283932879330793319933239332993337933719337793383
93407934199342793463934799348193487934919349393497
93503935239352993553935579355993563935819360193607
93629936379368393701937039371993739937619376393787
93809938119382793851938719388793889938939390193911
93913939239393793941939499396793971939799398393997
94007940099403394049940579406394079940999410994111
94117941219415194153941699420194207942199422994253
94261942739429194307943099432194327943319434394349
94351943799439794399944219442794433944399444194447
94463944779448394513945299453194541945439454794559
94561945739458394597946039461394621946499465194687
94693947099472394727947479477194777947819478994793
94811948199482394837948419484794849948739488994903
94907949339494994951949619499394999950039500995021
95027950639507195083950879508995093951019510795111
95131951439515395177951899519195203952139521995231
95233952399525795261952679527395279952879531195317
95327953399536995383953939540195413954199542995441
95443954619546795471954799548395507955279553195539
95549955619556995581955979560395617956219562995633
95651957019570795713957179572395731957379574795773
95783957899579195801958039581395819958579586995873
95881958919591195917959239592995947959579595995971
95987959899600196013960179604396053960599607996097
96137961499615796167961799618196199962119622196223
96233962599626396269962819628996293963239632996331
96337963539637796401964199643196443964519645796461
96469964799648796493964979651796527965539655796581
96587965899660196643966619666796671966979670396731
96737967399674996757967639676996779967879679796799
96821968239682796847968519685796893969079691196931
96953969599697396979969899699797001970039700797021
97039970739708197103971179712797151971579715997169
97171971779718797213972319724197259972839730197303
97327973679736997373973799738197387973979742397429
97441974539745997463974999750197511975239754797549
97553975619757197577975799758397607976099761397649
97651976739768797711977299777197777977879778997813
97829978419784397847978499785997861978719787997883
97919979279793197943979619796797973979879800998011
98017980419804798057980819810198123981299814398179
98207982139822198227982519825798269982979829998317
98321983239832798347983699837798387983899840798411
98419984299844398453984599846798473984799849198507
98519985339854398561985639857398597986219862798639
98641986639866998689987119871398717987299873198737
98773987799880198807988099883798849988679886998873
98887988939889798899989099891198927989299893998947
98953989639898198993989999901399017990239904199053
99079990839908999103991099911999131991339913799139
99149991739918199191992239923399241992519925799259
99277992899931799347993499936799371993779939199397
99401994099943199439994699948799497995239952799529
99551995599956399571995779958199607996119962399643
99661996679967999689997079970999713997199972199733
99761997679978799793998099981799823998299983399839
99859998719987799881999019990799923999299996199971
9998999991100003

Sieb des Eratosthenes – Primzahl herausfinden

Es gibt eine einfache, aber effektive Methode, wie du für eine Menge an Zahlen herausfinden kannst, bei welchen davon es sich um Primzahlen handelt.

Sie ist nach dem griechischen Mathematiker Eratosthenes benannt, der dieser im 3. Jahrhundert vor Christus diesen Namen gab. Das Verfahren an sich ist sogar noch älter, der Name wurde jedoch durch Eratosthenes geprägt.

  1. Die Methode beginnt damit, alle Zahlen von eins bis zu einem bestimmten Maximalwert M in einer Liste explizit aufzuschreiben. Das können zum Beispiel die Zahlen von 2 bis 100 sein, wobei dann 100 der Maximalwert M ist.
  2. Zunächst sind alle Zahlen „unmarkiert“. Du beginnst nun mit der kleinstmöglichen Ausgangszahl und streichst in der Liste alle Zahlen, die Vielfachen dieser Zahl sind. Da 2 die erste Zahl der Liste ist, bedeutet das konkret, dass du alle geraden Zahlen streichst, da diese alle Vielfache der Zahl 2 sind.
  3. Nun gehst du in der Liste weiter zur nächsten noch unmarkierten Zahl. Diese muss eine Primzahl sein, weil sie kein Vielfaches einer kleineren Zahl ist. Nun streichst du aus der Liste alle Vielfachen dieser Primzahl. Gehst du von der zwei aus weiter, ist das nun einfach die 3. Dementsprechend streichst du die 9 (die 6 wurde schon als gerade Zahl im vorherigen Schritt eliminiert), die 15 (auch die 12 wurde schon davor eliminiert).
  4.  Dieses Verfahren führst du solange durch, bis du am Ende der Liste angekommen bist. Alle Zahlen, die dann noch nicht gestrichen wurden, sind Primzahlen. Damit wurden diese aus der gesamten Menge der Zahlen ausgesiebt, ähnlich wie man nach dem Sieben einer Handvoll Sand am Ende nur ein paar größere Brocken übrig hat.

Es gibt zwei Tipps, mit denen du das Verfahren deutlich beschleunigen kannst:

  1. Du kannst beim Streichen der Zahlen direkt beim Quadrat der Primzahl anfangen, da alle kleineren Vielfachen schon markiert sind (beispielsweise fängst du bei \( 5^2 \) an, da 5 × 2 das gleiche ist wie 2 × 5 und entsprechend im Zuge der Vielfachen der zwei schon gestrichen wurde.
  2. Du kannst mit dem Streichen aufhören, sobald die Primzahl, deren Vielfache du betrachtest, größer ist als die Wurzel von M. Das ist in Anbetracht des ersten Tipps konsequent, da du ja erst bei dem Quadrat der Primzahl anfangen würdest, das damit größer als M wäre und sich nicht mehr in der Liste fände.

Zum besseren Verständnis kannst du dir dieses Video anschauen:

Primfaktorzerlegung

Stellen wir uns eine beliebige Zahl zwischen 2 und 1000 vor.

Leider weiß ich nicht, was du dir für eine Zahl vorgestellt hast, aber zum Glück habe ich mir auch eine Zahl vorgestellt: 573.

Wir fragen uns nun, ob es möglich ist, diese Zahl als Produkt aus zwei Primzahlen zu schreiben. Das heißt, wir brauchen zwei Primzahlen a und b, sodass gilt \( a\cdot b= p \).

Die 2 können wir schon einmal ausschließen, da die vorgestellte Zahl ungerade ist. Die nächstmögliche Primzahl ist die 3.

Was ist 573 geteilt durch 3? Das Ergebnis lautet 191 und tatsächlich ist 191 auch eine Primzahl, sodass wir nun die Primzahlzerlegung \( 573= 3\cdot 191 \) kennen.

Primfaktorzerlegung
Die Idee hinter der Primfaktorzerlegung ist, dass es möglich ist, jede beliebige Zahl eindeutig als das Produkt aus mindestens zwei Primzahlen zu schreiben.

Nehmen wir uns noch eine weitere Zahl zwischen 2 und 1000 als Beispiel: 222.

Für diese gilt nun \( 222= 2\cdot 3 \cdot 37 \). Das heißt es ist nicht möglich, diese mit nur zwei Primzahlen zu zerlegen. Dennoch ist die Zerlegung eindeutig!

Tendenziell werden die Zerlegungen für größere Zahlen immer länger. Zum Beispiel gilt \( 123456789= 3\cdot 3 \cdot 3607 \cdot 3803 \).

Trotzdem gibt es natürlich noch sehr große Zahlen, die in nur zwei Faktoren zerlegt werden können, beispielsweise Zahlen, die man explizit durch die Multiplikation von zwei Primzahlen erhalten hat.

Obwohl die Primfaktorzerlegung schon lange bekannt ist, gibt es bis heute keinen effizienten Faktorisierungsalgorithmus für normale Computer, mit dem die Rechnung durchgeführt werden kann.

Bedeutung in der Kryptographie

Die Primfaktorzerlegung wird bis heute in modernen Verschlüsselungstechniken wie der RSA-Kryptosystems verwendet. Genauer gesagt wird ausgenutzt, dass es nach wie vor keinen effizienten Faktorisierungsalgorithmus gibt.

Dabei macht man sich die Asymmetrie folgenden Prozesses zunutze: hat man zwei Primzahlen vor sich, ist es für einen Computer überhaupt kein Problem, diese miteinander zu multiplizieren. Daraus erhält man eine deutlich größere Zahl.

Es ist nun einfach, unter der Kenntnis des einen Primfaktors den anderen zu bestimmen. Man teilt das erhaltene Produkt einfach wieder durch einen der Faktoren.

Kennt man aber keinen der beiden Faktoren, kann es für große Zahlen extrem aufwendig sein, die Primfaktoren zu bestimmen, da die Berechnung sehr viel Aufwand bedeutet.

Du kannst dir vorstellen, dass man zur Aufschlüsselung einer mit diesem Verfahren verschlüsselten Nachricht beide Primfaktoren braucht.

Selbst wenn man das Produkt der beiden Primzahlen kennt, das man beispielsweise abgehört hat, wird es kaum möglich sein, die Nachricht zu entschlüsseln, da man dann eine sehr zeitintensive Rechnung durchführen muss, die auch mit einem Supercomputer viele Jahre braucht.

Der Verschlüsseler und der Entschlüsseler kennen jeweils eine der beiden Primfaktoren, die sie sicher zu Hause in ihrem Tresor verwahren und keinem zeigen. Damit ist es für sie viel leichter, den anderen Primfaktor aus dem Produkt zu extrahieren und damit die Nachricht zu entschlüsseln.

Auch bei den Kryptowährungen, die heute rasant an Bedeutung gewinnen, macht man sich solche asymmetrischen Prozesse zunutze, um effizient verschlüsseln zu können.

Außerdem gibt es für sogenannte Quantencomputer (die aber gerade erst entwickelt werden und dessen Entwicklung noch in den Kinderschuhen steckt) theoretisch einen Algorithmus, mit dem die Primzahlzerlegung einer Zahl viel einfacher und schneller berechnet werden kann als mit normalen Computern.

Dadurch wäre das oben erklärte Verschlüsselungsverfahren obsolet, was das Interesse an der Entwicklung von Quantencomputern durch Geheimdienste usw. deutlich steigert.

Beweis der Existenz unendlich vieler Primzahlen

Schon Euklid konnte beweisen, dass es unendlich viele Primzahlen geben muss. Da dieser Beweis sehr elegant zu führen ist und eins der Musterbeispiele eines mathematischen Beweises ist, wollen wir ihn an dieser Stelle nicht auslassen.

Um zu beweisen, dass es unendlich viele Primzahlen geben muss, können wir genauso gut die gegenteilige Aussage widerlegen. Das heißt wir beweisen, dass es nicht sein kann, dass es nur endlich viele Primzahlen gibt.

Gehen wir also davon aus, es gebe nur endlich viele Primzahlen. Weiter oben hast du gesehen, dass man diese alle einfach in einer Liste aufschreiben kann:

Primzahlen: \( 1, 2, 3, 5, 7…n \) (wobei n die größte aller Primzahlen ist).

Multiplizieren wir jetzt alle diese Primzahlen miteinander und addieren eine 1: \( K+1 = 1 \cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot … n+1 \).

Laut unserer Annahme kann dies keine Primzahl sein, da n schon die größtmögliche Primzahl war. Jetzt wissen wir aber, dass jede Zahl, die keine Primzahl ist, einen Primteiler besitzt. Es ist also eine Primzahl, durch die sie geteilt werden kann, da sie ja in Primfaktoren zerlegt werden kann.

Wenn wir \( K+1 \) nun durch eine der Primzahlen teilen wollen, bleibt immer ein Rest von \( 1 \) übrig, da wir ja extra eine \( 1 \) dazu addiert haben.

Das gilt für alle Primzahlen in dem Produkt, weil wir \( K \) schon eindeutig in seine Primzahlfaktoren zerlegt dastehen haben.

Wenn es einen Primteiler gebe, müsste dieser restlos \( K \) und \( K+1 \) teilen, was nur von der 1 erfüllt werden kann. Damit sind wir bei einem Widerspruch angelangt und \( K+1 \) muss eine Primzahl sein, die größer ist als n.

Wenn wir uns jetzt noch klar machen, dass wir dieses Verfahren immer wieder anwenden können, sobald wir behaupten, dass n die größtmögliche Primzahl ist und damit eine größere Primzahl finden.

Damit kann es keine größte Primzahl geben, was bedeutet, dass es unendlich viele Primzahlen geben muss.

Goldbachsche Vermutung

Mit Primzahlen lassen sich viele und interessante mathematische Sätze formulieren. Ein berühmter ist die bis heute unbewiesene Goldbachsche Vermutung:

Goldbachsche Vermutung
Jede gerade Zahl, die größer ist als 2, lässt sich als die Summe zweier Primzahlen schreiben.

Es ist faszinierend, wie leicht sich dieses Problem aufschreiben lässt, und dass es, trotz aller Fortschritte in der modernen Mathematik, bislang niemanden gelungen ist, es zu beweisen.

Da die Fragestellung so einfach zu formulieren ist, sind Versuche des Beweises dieser Vermutung eine beliebte Beschäftigung von Hobbymathematikern.

Ähnlich wie bei Fermat’s letztem Satz könnte es sein, dass eine relativ naheliegende und einfache Lösung existiert, auf die nur noch niemand gekommen ist. Vielleicht fällt dir ja etwas ein!

Aufgaben

Alles verstanden? Jetzt bist du an der Reihe: Wir haben 10 Aufgaben zum Thema Primzahlen mit Lösungen für dich:

Aufgaben

Sind folgende Zahlen Primzahlen?

\( 1.\;21 \\ 2.\; 43 \\ 3.\; 331 \\ 4. \;2n+4, \; n \, \epsilon \, \mathbf{N} \\ \)

Bestimmte alle Primzahlen bis N mit dem Sieb des Erosthanes

\(5. \; N=120 \\ \)

Bestimmte die Primfaktorzerlegung folgender Zahlen:

\(6. \; 55 \\ 7. \;65 \\
8. \;120 \\ \)

Als die Summe welcher zwei Primzahlen lässt sich diese Zahl schreiben?

\(9. \; 66 \\10. \;100 \\ \)

Lösungen

Lösungen
  1. \( \text{Nein} \)
  2. \( \text{Ja} \)
  3. \( \text{Ja}\)
  4. \( \text{Nein, da die Zahl auf jeden Fall gerade ist} \)
  5. \( 2,3,5, 7, 11, 13, 17, 19,23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 \)
  6. \( 5 \cdot 11 \)
  7. \( 5 \cdot 13 \)
  8. \( 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \)
  9. \( 13+53 \)
  10. \( 83+17 \)
Hat dir die Erklärung weitergeholfen?
[Bewertungen: 0 Durchschnitt: 0]
Manuel

Manuel hat in Heidelberg Physik studiert. Dabei konnte er sich davon überzeugen, dass die häufig getroffene Aussage, dass man Mathematik im späteren Leben nicht mehr braucht, ziemlich ungerechtfertigt ist.

Mathematik ist die Sprache der Physik und damit im übertragenen Sinn die Sprache der Natur. Dadurch legt sie faszinierende Zusammenhänge offen und vermittelt eine Denkweise, die auch im Alltag oft sehr hilfreich ist.

In seiner Freizeit macht Manuel Musik, liest viel (von Goethe bis zu Fantasy-Romanen über Oger) und reist gerne durch die Welt.

We will be happy to hear your thoughts

Hast du eine Anmerkung, Frage oder einen Verbesserungsvorschlag zum Thema? Wir antworten – versprochen!

Pirabel