Prime number support

[zak]

going to http://www.wolframalpha.com
and writing primeq 2113081902.... gives the result "no prime"
but writing factors 2113081902.... gives no result so they fails to factorize it, it may be of the sort of numbers used in ciphers which is impossible to solve.

[zak]

Johannes, your prime numbers functions in your module is useful and it gives more than other languages gives if any. and we can use it from within thinbasic with more digits than normal, such as drawing primes spirals and more. it is said that prime numbers is a gold stones in the desert.
some times i am using a console program factor.exe from:
http://www.shamus.ie/uploads/File/factor.exe
http://www.shamus.ie
its usage can be like this factor.exe 123 >> result.txt
to output result to a text file, or without ">>" to output to screen
like
factor 201487636602438195784363
gives the result "this number is prime.

i forgot to say that with very big numbers the program hangs, or may continue to calculate for eternity as it should be with very big numbers, and the only way to stop is by ctrl-del-alt many times.

[Johannes]

Zak,

A single-purpose program such as factor.exe is most likely written in C or even assembler. I will never be able to beat that in something like a general Big Integer module.

I myself have written a program to calculate n decimals for PI. First in pure thinBasic, then with certain subroutines in assembler, and finally in pure assembler.

' Execution times for 2500 decimals.
'
' Pure thinBasic ________________ 4,64 s
' Set number in assembler _______ 4,60 s
' Addition in assembler _________ 3,74 s
' Subtraction in assembler ______ 2,98 s
' Multiplication in assembler ___ 2,97 s
' Division in assembler _________ 0,0541 s
' Zero skip in assembler ________ 0,0472 s
' Check word instead of string __ 0,0455 s
' Calculation loop in assembler _ 0,00653 s

The speed increase from pure thinBasic to pure (32-bit) assembler is a factor of 710. But even between "Division in assembler" and full assembler there is speed increase of factor 8.3. I'm certain that if I were to write a single-purpose prime factoring program in pure assembler I would see a speed increase of factor 10 or more. But writing in assembler is extremely time-consuming and defeats the purpose of the Big Integer module. If you need to factor extremely large numbers using a program like factor.exe is the best option.

In the end I was able to optimise the PI program to run in 0.102 seconds per 10.000 decimals squared. In other words, calculating the first 10,000 decimals of PI takes 0.102 seconds, the first 20,000 decimals takes 0.408 seconds, the first 50,000 decimals takes 2.55 seconds, and so on. I have a file with the first 1,000,000 decimals and that took 17 minutes to calculate.

I could do 100,000,000 decimals in only 118 days...

[danbaron]

REVISION: Stuff in red, is wrong.

No, the 112 digit composite consists of 3 primes.

http://en.wikipedia.org/wiki/List_of_prime_numbers

359334085968622831041960188598043661065388726959079837 (Bell)
43143988327398957279342419750374600193 (Leyland)
1363005552434666078217421284621279933627102780881053358473 (Padovan)

Actually, where is the average person going to find those really big primes from which to form unfactorable composite integers? It seems to me that most likely he will get them from lists of famous primes. So, in that case, the best way to factor such a composite would be to make a list of lots of famous big primes, and multiply various dyads and triads together, and hopefully one of the multiplications will give the number you are trying to factor. (But, who wants to do that, unless he is being paid?)

It's good that you made the module. It's not your fault that humans can think of computations which are far far beyond the current capabilities of any computers to solve. I think that part of the fascination with such problems, is that they deal with numbers that are much much bigger than the total number of particles in the universe. So, they are not really comparable to anything about which we know. They are pointers to the infinite, which humans are naturally drawn to. (But, if I was making the module, I would have anticipated the same troubles - "jokers", easily constructing problems which no computer on Earth could ever solve.) The important thing is not how fast your module is, but, the fact that it works correctly. Additionally, you, like Eros, are handicapped by doing everything yourself - you don't have dozens of people all working on the same thing. Anyway, now thinBasic can find primes and factor integers, while before it could not.

I never previously paid much attention to Number Theory, primes, and factoring. But now, I see that they are interesting. For instance, we know that the sequence of primes is infinite. So, there is no limit on the number of digits a prime can have. It seems unbelievable that a million digit integer, could have no factors except 1 and itself, but, it's true.

It is also interesting seeing the various methods developed to determine primality. And to realize that (as far as I am aware), no one has found a fast way to factor composites. (When you factor a number, A, you first try to divide it by 2, then by 3, then by 5, .., following the prime sequence from the beginning, right? When you find a prime which divides the number without a remainder, then you have found one of the factors, and the quotient is a new smaller number, B. Then, you repeat the process for B. The last quotient in the set of quotients will be unfactorable, it will be prime, and, the factorization will be complete. Of course there is no guarantee that the last quotient will not be 50 digits long, correct? In that case, you'll probably never know if your factorization is complete, yes or no? And, how do you know if a number is unfactorable, i.e., a prime? If it is not exactly divisible by 2, and it is not exactly divisible by 3, and so on; then, if your test prime divisor exceeds the square root of the number, the number must be prime, right or wrong?)

http://en.wikipedia.org/wiki/Integer_factorization

And, if you think about it, you can see that it's easy to build giant composite integers which are easy to factor. Just multiply together the sequence of primes, 2, 3, 5, 7, 11, 13, 17, 19, 23, .. - you can make the number as big as you want. Additionally, from the proof that the prime sequence is infinite, we know that if we multiply the sequence, 2, 3, 5, 7, etc., and stop anywhere we want, and then add 1 to the total, then that number is prime (I know I am not teaching you anything, Johannes).

For instance,
2 * 3 + 1 = 7, is prime.
2 * 3 * 5 + 1 = 31, is prime.
2 * 3 * 5 * 7 + 1 = 211, is prime.

Why is the number one not prime?

http://primes.utm.edu/notes/faq/one.html

Below is prime number 5471, from

http://primes.utm.edu/primes/lists/all.txt . (The list was updated today - maybe, everyday.)

It is equal to, 7911 * 2^15823 - 1 (4,768 digits).

(Maybe zak can see what Mathematica (Wolfram) has to say about it.)



1246960727254209790387723579944578027302422003781509348503447323762475755173375244229550995867793645537545707286945509846966992771567951909913727489880115890646648041084352251368946450984551401239294760128446119108745511061333429892413564649516277469667788551464086423150878887320321746524584154391078893771656421508583123681615124121209893052315387614429855284548372514322098934273072682343443264845392694411453014180586746916318510688843451594444309735447066581723660977279435745206923637972688840286436731662278887967084585641033238200695458063582412324793266473619894777773535770067653147777370232404158890756835744630841415460047706813636023258119008312231220513550639574273348385465714214575028069456338269717947511453962719604798141954524491069573776978943660209920217545841323558118292154793464304655468898218811787785193670489578489234017465337674951672614885353089996365437504933317226563305660415429788203003521422802603146198333405957317502783313353766476327612318895552568378224052997673208959589558344708007246268628048504468852626730487766922791987516686660480424982149916033748626425405790944375213551878048117297253957550648473930922044034179652947565368831202390064249960139312370665296813930030995435109575829663497629941538270810359794967077848031038593484194221036578013473630344836507333962141288394566380487299463979343518449201461817083543501176829592689364354187233049009007861424601477405915705910816649757120341670855720870019605115841474412657161427770160634224056956169703432147767402776293550682470783431174623220605895152390450115989649530293013110376855071050276234607480337678067248719318853207102286273587649357762062429224383925615142065619817812037319469086352091861392578954093133664302134614858869332852032759088478737616072826991598161931096209845116298969191591567954560251779251082353462046525273927116216661473449648454552099332294793707759367266075984446121839355768115306511453637663695560046057880275997004276141568653067796729006641013243897331134137089780459921316215797242115141228284578300889980954245325514446696379634747108318850938644763918001236007797216298144889217135459681229088798101368405486520232628988022829434644349888689736651966250669502680320244032110647624218536383498823678430432529690485983466352207596477570206369187988782433128192901629041498478069261136595860774869820911469018766767582063402658063048215944975902100603119286795186680209512184219835988749067879794595551543980682169854177770591347678985578452213954457630483338379970026507816228033610323205492144654291746331655156179490126424375460956072118839743870451974719972610619650283999421086500197159619650071305733491222204103496120012681337873577243601532128027323309966196909818642534864611741033258610307550364100297451318354694419724567628063531886493017065092157635844400881600028232912155717844677191843509512357307488708476336081132206709806307041783165008707827566573868765294241313106662484992736820423797542656595774826192976843342158023931258294114037299002161747370235164286500946157401150403617025989422981295218965287006352432821934123405687055299421927086191589057381273035017444444514984840738908314056633103053809914554220456934165467371298588094156471010276807095313056449055210095668810869121560663058690196809710854764785666326804033001453469764410760283546442890478371893717153951624638285020510065512584984810495976202467715981436013270100469638802300732464163202702170840286947150214516151486381218062322264585036020575880190692319622404864424687150560986163247107734007091894941220986627570945416385792722772597270465228853886349730219772301992424603372223449354085317904065372641145190464619658082701193867984401924897351648274593928241826059823289182813888510340229562603728125425157810791338298927276780560693922483512529141460026247576165369402161873979977354597913541530007584717912233179089012699023461881288418173162845933032728166960068593846338611403169324702160760071557831237949532982427474974973927938054968327626526038573839069904971294846149088115794010255149108054346113031254214841661585787253013506381816829232936842085232666946537186482951167677159294869452805751715789894635118072961717424548524459207497252890072781660614102803931146420202753151488190966097886033617164689086047862769597876747251236121871953357498221524395129849254523136907590754519467382208190276932324328741599143726306370900277881315642819350336370709541003576211513304582714511684424649877969975592569148143563817102763308432529439932629747027978116575222205771632146277091973257984202848499303657173996272482812848803276122767380783040347464829147451739007248522233466766984146752981677096652646107316406625267311881989938038708638402666346951158260044878535563092323869250281383878865571387729504834701425134610455461887

(One more thing. From the list,

http://primes.utm.edu/primes/lists/all.txt ,

the largest known prime has 12,978,189 digits. The sequence of known primes must have gaps (missing primes). Otherwise, you could multiply the entire sequence together and add 1, and that would give you the largest known prime.)

[zak]

it says True, as a respose to PrimeQ[7911*2^15823 - 1]
or PrimeQ[12469....610455461887]
it lasts about 20 seconds to gives the results of this gigantic numbers.
you can download a working mathematica from here to enjoy the above result:
http://www.wolfram.com/mathematica/trial/
i am amazed by how much powerfull and versatile this software, and it deserve to pay for this software (the home edition) but after i got my first credit card may be within a year, do not smile, i am not alone, look here in quick basic 64 forum:
http://www.qb64.net/forum/index.php?topic=2632.0
someone wants to donate, and from the amusing discussions it appears that all the users don't have credit cards, they are old fashion good people .
links for mathematica version 8:
http://www.wolfram.com/mathematica/features/
http://blog.wolfram.com

[danbaron]

I went to,

http://www.wolframalpha.com/

I tried to enter, "PrimeQ[12469607272..455461887]".

It wouldn't take it.

It would only take 200 characters.

It stopped at the 193rd digit of the number (..455401) - it wouldn't take any more.

So, I don't see how you entered the entire number.

And, I wonder if Mathematica would be so fast with the answer if it had to use the number, and not the formula.

I'm pretty sure that Mathematica will use any trick it can.

-------------------------------------------

I think that anyone with a brain does not want to have a credit card. It is a million times better to pay with cash. And now, a person can use PayPal. The goal of every credit card company is to put you in so much debt to it, that you can never escape.

-------------------------------------------

At least now Mathematica has a home edition, for $295. Previously, it was amazingly expensive.

-------------------------------------------

One more thing about prime numbers. I have read that mathematicians believe there is something very deep about the prime distribution, about which, they currently know almost nothing.

-------------------------------------------

I tried, "PrimeQ[1]", --> no.

And, I tried, "PrimeQ[2]", --> yes.

(I agree with these results.)

[zak]

yes wolframalpha does not accept input more than 200 digits, and input PrimeQ[7911*2^15823 - 1] gives the answer Unkown. so this is bad for wolframalpha, i will post them for this limitation.
but using mathematica 8 it gives the answer like the picture below. in mathematica ide you can input numbers long as you want.
mathe.PNG

the exact timing is 31 seconds like this:
mathTiming.PNG

[danbaron]

I don't see how Mathematica does it so fast.

OK.

From,

http://primes.utm.edu/primes/lists/all.txt ,

Attached as a text file is, prime number 5077, 2 * 23^93337 + 1.

It has 127,100 digits.

Try it.

No. It won't upload the file.

It says the file is 124.1 KB, and it will only take 19.5 KB.

I'll have to try something else.

Try this one.

Prime number 5154, 33759183 * 2^123459 - 1, 37,173 digits.

(That's all for me tonight.)



245825316648835246107086700746622739893249151204659010605619885962415420636650276193441794304209340332252152427318296859014402072732650302593371809176729893538427554644693797938667185584755297779200302381424976923320768252998452346192381338164546097080077718421061636131884014150976460657468696760679306211716680216225887314637541932777904158218149835489339571973703276029064127072720893102640412194311825528289010145307299064971915350548052663757807749521139082765544145936291705968079895123313227320381846809485893806169014400839353464343790903361394644861489087017213606605039279035041099524534364978648657701649145289519455533531838954628192863718427810229383736586846915017860956571202498855525174343303514262515296273812634223904988976122905294628376397501915597103930242031227785458514921047258676583889291457436977359516684278187826261956070695531239273461152618402620730952195609280212234560159438613657982488655590071795674104568322894574829879117254950163321820009357507744413806536843069635679984380800738603196109176366098686796815081725852733970835772414938822725755280481674945695355463770760263409993341363086851002614123335909447592930271543614985732615272613130572152772427120875289370112290675459235385121658236789731830925041292256057949462981812979669678255170860925991459896226659504484135242387925332457067578103073336921093306904978058889614591538632787757752710988792900145394494519911216492647009911020914299148338343521462876287414650273925784769553172315043687178083558839385215196042203281299065885607932335502091205244223948174418002100183906779773991760996312426103546985573469047818144279445747010619167321055091269747495611462030173800636014212816267856150735513505430584901646778709146063686624051721341620737959626727490766450268760703572286291795693674531658588819186571904150583816622345835510122499358019563567047520569348485896785099041078575481591381015543219190005216261259106374006515166417492536614328541177020312030556915658313983334262481774003557133868869590991616220090054721873323954766376718115297600945071904301589377577865047867033271875092345536059442695495797877904240696130038174839681656776273437506098580496689266126233889649354109508396964191574091002545974037667877599210166739856494076045584159398553511222048201945954839673780808086578960447886287822811744075119237526715358262528839714283028635891234156676087551395811093273362431249798126145323224679715616154981321704626852534912421740619986979569881742565383559703622341461852732564460369198795520055749481891619817842747803652275108825219000445672775770780019080302957904180349996303453580616492996766138417202269397826143108651808670758988738599462248606807906746117823193937566686628735618489819290622459946736890031265572632164314660602199147226574703442560249886457602248511547077781963448326966693098908110651315316137291028848998548319306014116169347251881769738729620029515323185727651051429134537063405508290002195415116843400559726938539512900345942243021191561647297649495904096107150966265804233576681017253013523270767682407793165783003449828687638349653091233818359724579834977579885016614408937720102845926759193075566282505719845910276502508148266820717928144246101495703977353808146861816763524873406505583681424947708427517998285620889901214507102047755980534903106127755887901649662400633475100999194186541493546253440639163560237865422555411843836046522305820390825440984579292735660185515078019813938623611314078854368516807044663984995902714170704034543511931668891231653743721565190660355387974576172154597402649455493184257113042496129420396894455429200713239380530521300795711364320399410436728430018724253687817266612842511662343045570709876295235129443879329509921783167480065092563023858125627861844737193796143537685851111332214455760302073866044436667686050729479755035806843621863385414781645059363177759690097913729925055617429810075420884324106143071349046761977349994633747254689040114192676949799541700837943631254089353966243170059288582127511021345447735488122946111376393635739798191941545421503010309091912069981453052169204055626689627481857191912883203124379809860095109872271955905318201976004217158442310635583922922966624014292090274747650408624307180597290743106629776980771400218400008606258461702613883504418532072807852109137115689658192935513927624055846782195977252908092752576252083323236675402393537146480748565204594819285892500669276249147421902971888047542349067207463055134509359881068661320910424651431466583015730520057320809223360353891886104982533002121075436685482377830881775429060328566006807230213816088610745400169083951677319868460887453616666610704038048278167259141188916779359137356932825716551032075686833604629209165723698073808417426231375369606978860868288536080162621394345769298886397768695152006906729443493164686568601634407325772244210326511609806650429461225698511676292457706363617978472187599153851919350408653337108551239380676204908670914109212135494457429678557304043817610439267890413336005802293081987700431810820254906572962837529579628786961288368497041208575013017643721603316064926894967783556586906259518676889627709953784796223319476584040016040200828479109818469533064455343169195874694337715799328344586865421223812978025766162580710433134606527188925735618790220996937137387581410597526523997224879016197236857938939538058806917897275862628133447798228708183860765056218331098832130456966465098367632042664034525907064033605697744245533194025077520096338688951086130720021983561734730603480823149071887865695652654140417994187733443787713655357389713964328313359905945942095522817852725353100586164126828586183551050067703130983981160116024901517971863150453214043087587707318830734301422281463151082215926413600345819478085064810776878950062939290226583335688898114339920005648692489738705789266689950140980896585730135982534291118395268217826011814607294396642605266526995731918176196168249255267434145174130685250481407728778991583210671340311113353671257332963226564846576299814095280698919993239985083803325468425613255808807246668078914837805640352146731989893960544251003418644240908373156736400119159917541468693788221145172919572372688793002997805811042863491288289005948031090770011766667642372630512011880437006516863924474625938410512421129466971233765648808419738560993306938105963772621903750760808239018868299987994306324889455390372719525772449667821378510788097508053312879562878321935891614064173519009898664704962467761052005162528951471903584579935062590662157220652729849907428741476646492505013014075071728641512769559249002213035782873751445781889568682371643601334848357175034673699822354521576416403752935259185156008557288199723740746392032261195807454688088074319994428256020724708858445826203962584076878074201276946770358642424979699011423607267945799845206854199792235508816638002542592346036815619115080091673799882214132974011670598794937849229756307975533673404718629683994853913488405818213105930809389255823724296548235225191249874622367955390465268849527310929917682765548934429953577757485571984985002541039881001795086497102511854795858100910338712150398663575603574837998692572295882528141186326986758604705257687569197460833836595141482722768067008409043544992594350691831096178234523036852904166429871237654053748037775525845316037678731569289043484723822938556342674118957412232412675211626466805423156855223190420032530378148088753618014195368095779974067993073549456450080302759458753319019147978193624171676246512725438388944779063638067863195141269596263851252169854529580195329355646742257441861000448814615705006320197596044236438285069688612155903875881016624169914721081909370290720214700151654763416936172125037333163919328846471401259242343597897302770107810691813802292524321175074504051061783654222879220070241372040735987749942037509774243346160830610416067082213618723869812831379117605059806180518559864859211362139521724002163391469936968174660361659509698289258906792246699915752753288445969158550758758092803610865956870353767172041926760824864630541462069205903631809320495828449517497035783507815731764546910895813360886959593215996134690650523463599062783201947551400697270579478050337433864382660346992343069164895997348146855679822453867930644910141775564802715862851584774112422543713374486037918991460049828425107176849698553341731620431748257506065946471136098147153416092995797115414636740650309019596681873009005323007812930254462464670012517106111771903065574416678519083282543040754644573817922699252950986844264029334248921295583811182577854417122012731971459220232796315289493299342204568975212680198707504495807520005578370314923333124505210021412385521187305777052007198270153850185241815595314863199708355798642058965805170483686363724192273683744173437789284152969753003182359628231809993718669705903999105988384364120393175240273245559224343796204190659602043826437308486263605410978044363628647290341640515081358140797838475266662062828433684577025465576196957726759884807948855087481150199934237918954896006386549382595357073578669202592199746077095102168068588948090606752156980532707353628567916900571208093142163855075990787842601922676380485470546446063803734533626547297954471575115529060497821579005484256391532531879509635569982396088540838464606135260660211956628385455039893596224367220491919579309480008613715190276919660965001208627656419554220198869217476501299423832619701084004398572752417613264133042710337447451702047543745708604758473970298349531393483774021537983002749291471662191596462267644379922493731676417228022749280570652159021057720207481856583883373712209436534950503785170097630158793815478372000072433581932517982993614403661850916620829656859646091357275136240421949506011129186373256318263487032554571111895563713552921958135181446444214718823993508780949580855924182321875661265784871802035035614144319123011211239943359201656981826695150239991963643274149429172130088518656544174331017051057738372636437275897890512545898043318145781482452585363377137255933139226733861431903683109631048215285144287931378176633832016522555547287873764242841428280428039875809724922843356698246597611195385116805008282899859165628077857071888492727457876141365753982079602274150609192868414206297040466684706063986457210842854055959539149260197483557433658429211427328113176953142928294746939069466876139900177618741878582385637887611797175353736589851267084111331479098332299736179101839177083242668114919052040906695379082055357803775642638516745125759455283757634607612572658334476374186916047147342972576864865228708191277949246301416362078462734433008277678412543841531828098081513094653822202422317098989563455683458239184318684887593359417572019599608152582509092580947012223721221008470883755683174243376455248584619457002868367607639877896219083720008829192951475946891821291585523746772844991413868438313095814145672041474356038866642271756657279815504422677713638245794454343744138048910082228919745652675025132054537872938310453334144357693974793119635240489470316446013300245916402267597793049495034274472613973775318163875739073671155316924371679331266516393272314597725204506732896683245520881812112062130398929822263671047165802042281769147137512069872023105473861010199546731695655996645420610094637156904361472860280650068687345320748384330668531037726008652663842084548500721708570857221275617554955552545986488342405818293035562509336978674801717430235412061369784562082957002122601647668022423435756180379697665722048287188620119424486415173389160217400093365019691970322875380676630402419185952347683103881229500191781588350553119595827618341368919346700422112938485637716308680670712664462978713413656114778139937255859955290823444470042988884489934867966701497150025009968953087002400201841490270782618710946175100813434623799473129655786045363984243315519649035303196627996383172175778298797648500647447523872735658223221662635812058891570386820295408829863180880815902552664842968182179776658889806681230697803524999434593804930394838988155986385979229902463926436216800438486864235430832285434131287050746925864494769041896409816374367104127735482008878425415329869623567537218553927510712672446622604518585825975506675632321280264016513170077719168327148734445319035010764400965093619661802898994764509992852868163543565728539735755467714290237971129249651504307195511099638937561027868130078155479695824948963891651016227185057679685497774248413621697972016751108199593047576686043563049334585819941930544582917886582953889587126589319004238940487658121513619189899698297042070007582157779257378945203147809417012874100262242850637580104426204648950708512200917513878091843269952372994775462331346884236078383775872987823533458225053359539984696707686758041922751780002336628432904832260779339401076766818817785365059662840126988233772787863038446076419104279286865123480391630942641161204435289985341664521138984624076511729365543467571831254316679343376976661851408570188189623697284358737229035184191716175950566527583622955439018449050738825866681484559702698643467476386033511986994560492626524157617250619245605015564216308708857204908012804188300056600217020667343700364242523288195257762905190871794674826986398918264167181479669262138847476183426920936508912379200670992988147533510406513045740024400472986870480562880664842844390411825463187757333956576911470944976716235246404737994567931047966439115050111712709167437261458825475066026801559044739669360490907525234805399882681747085153575356689826944336820178551450445476745720236379487019385101381088058145267019645078719201481022151120571029387371195317098541954365291444797016257360079322715764890688283805733850162386852991437530422679222834502897994765335309097793598412434283977717329657253838493677693996211320376276282333803604366603667519359407021876920692242675130724603677578419644396811518261182300464318942270362748719877542100621093035021881748320801942138397427196253837426327849290791286876653841216326881257622021032459100787263037706434468976746715093336085314604684047843730316316913955806513330838105775003080277592981364331001630294962525870517837145811198656075920218485413713775894131329437667646584665303282285719202844367529703442200467169150446893190565950879633895801375588253495332479950887221234865594129726896418066601077569490536901925454998801838142729701435322278981292767707312886014711734823527118448310613532291009344268552794265975529042576709820814149464241487353808859356722303082206224178724168816865564121018019234408009109868848649213265525784443047499382548196104142796480958470618414725748585988011449754737554596944147676507924722807742500032020511717087833062329340543484977163695261449862265946297016375837628588466560991121355284557120957008955300714383292570791751018366952778813576738643436010274437651759208991325512752446269088843910921853021791690372948207502003458108703796121222012172137236134037032703566490996869969731151826219435209976920328152231063489263873664369812404258472257932145414896310756317586599422947256082675693330723941255807636134349530236363579051621003129409046937167611788720503312667444476419599640593879445337625798547961139079915459203148239491405868202581276776383374998197095823046482562999645729873667322361782483185660343097626638631109377748079195521193847993937124479143835613620991665851720247247814238520276130631962795041090633981590911154913906907490506928660497122558778628138404816458000082159851496023162684668204769094929886304351542554077197851855397799826191380943779149562073206235478432297992481259164357640571426529144584240490303438857537379850827435114049139903466494302972321466228676819292659693583047834600649387430535781986064741980994722978597047732594727427213098112678097862054950476347300604265694196086338578990428561417228667637999638756864652467628564275982594741924147824646371504716456089330050767617811002116673304712547313729159786725730017993111273335076008077582147995802814044029369480188453045295114011049840419790315847323908627029441626664138125045784954280082982118988515891225643675843907594721822171487151609456896512878184960032158574876391000904216293623946516347892069133697037333848686910754405152423871770681705422171931582815610380462971309889168367034946425177220808050553442084628713053034655201105985601689940768462307314888600009331595867438379645620983460509569911724534263501374573789284047636518308980299131993921227793515911033989029359699220768999447713468781927025251924467743890218650238895323953999225223265244897965708844950266401407326011017452588611739350396067402360160682096652169232440493084170019650416304967579182518403041043023522373765744075792910926640482707023664721588109502881835295275152254565793704167834456107737846354517461022506748090789815876170328622010418239543188538995948434221408012046084168338254321873301580161651131409587468332696670856603843771576033687234999502851704557179119030560604916068745072759351278982901418746381407284588907872284574517008779740231277246940083579388534187778119635275150977286962753894192087607782513996382686791895133929850346248408533430193013912306964012917336974424279402215628395287318645062253142141587609774966724866908352104304887407598516820181179400857352611177440355969399792981154124398534485671383597461575687135822131373955945532927527257465868665328713391315987420137582228944910394936366754171953558240942916474079837456063428628952195745469924877877227489202279655394343651864037102286592526984644059671906769799557437092585718179386487013482557687410231009358332701219437382169714873364120044551339413991078495048166976647315205250134244244426130765589301710257778538711168106880843893355676948878613113357972754445645840543560490805495083697467352964118894038205038931180713049941377609061673046462249655739100344383524688523152846512743340434850947383917914572089598031462386131531971043616322331190788280523883515665887109187927635654909981467407877939311092380443426988131249977976009851066859841636235372073409575586228537772599088778991985323030168081446594390526275256487121017477199437085804781045116872946716893596189143619365093951363671805656925473909350526330492547098949675818587958357961728393351865323052331675331164649887523788936399114381385073115837028709288621834339570219094003034479529514475716222368664180447292204564381613462367132958953811670923072200502164480400623686153483787461019386382271750998074165839443704076889302584219783130162743584890671411720447572787785210663322874117611080355449057986848768087996025825711088714146381695095631764930762304746137858024868168334547733088736325696167127461327968225710789500177404542820939040873714818833380576742243079081870085308412106909881190730929030673715867114406811843121367150928622891368735526562588235772156256286354293593239824615422286443704918834021628038250904887094143482573017610714760770421839590078712437936764252811790246244814393854479524771678195446347446558302713507550003543025565146112568079444269394781097930586685118973669194771030189784607661302667922594089183347691511936877571519990510461369091458776560033086825158630005597374630792401927004213067886310082251317780852737860315346649132014530226299521979765810194224951068344227154441967773809244264406562127963047257474379782604492835548206756618665050554201384206964635598653915737608188382231510101615801508143918514302708993881992917560599225676041731057732724676929977413803279121878875449190060670406841113664528768528089892852906854714381178997931058063315461698215715839281250284518316431492288922692024563935757860325904917919320825456096854247267523954486031213615172543978493626960307806692205619718620594469011501970370820615938681376148771011953856593796423563051794707504407032027974867121579173376081057902529613125240924730284331900104771275783840004109354769530021905156013848894119432828674164008930127692554623817267605861517016900800075337703841943745290646687403924392801388294071306175219130929497847042011287971200407320751226482000470917927149056604412368657065165301294998858587111068980657097435236568953350324266756823644929907347744846577325693338640019257708022994963536201329447108676445770525275249059220969297088047096437365592302500545917261471801158714390210320248791362027378038170910458386622285104785058585470397451556971270170623540076025392989974271524617052532195982828700289491960998094268677011712942090537797746225124292119111319754260973437593451470509154947782099521718144313602045182810223278586665375711721974828399520874972964636829422393089758278296364447059849161527793475685857587123435236031602516667556581161790843147272016340440462243448440443384918063081427619736014118635158617617716752605396217332392686840450872913234237710982633463369493020520336738608175388829332730022240216036704887772138537920411927007556977891627341096397119592501474408871354585795279298831501949865665473582574858018375933606303023064011954001352453780246005014112146061981472970559735889144944918494713690600541464426781210247286720215292149201367862794437027129592409515842931850083975144954503882782312508947793842681155806569589886929702273436499325288231193152207757364702192100237229259166522253183428636099655212763748938016262084760440619953566665685717802511412141909814993928238766715363304308792386393368062845975260625336623965138245396613737169966521757692173553341007204053923336806663501662225967956081025292360949692725266783342372524399555363584012094910267355192819120207120590122579112215586635184590157822804973718724570639388520551296831387597706437258050029886398969414458031942541838844233441230972186312221984123268840455319795534200025393307023138542080625813681261998297719178148006438645680011188315798675022063611363123548980037330372483379596051431921165446745929487641342181260732962015333258927213628186974561304782437493431675122793302118441015100866548771498584083818784038462243164167072498925124081916086092977022727617721735887799794415079620440960057241962133529492888707179745050158999899705725143574613598047246133542955177075020748802605314558414308840364286726456466691720855791229690369059884557536137932941611439305776265624183601251465791038895670209699365315246223487961778799247243932472771495761613497254777258267401556089532607063520530926124412050380188168431318355988830792092591413174097463807661195528447941443546766158739575006704809561569482493704877077886152344755627043057032865444016258460624777567725553438632130536254236107201143093905305466174442456139427489736339441570317117945327943061559730545287169281960275147319866541012679011374447671043035083050414574910449386470569737026476593644122154315305931133026531028670231638049758235440339130579601702965922590001930171145644632021568668582991037691619362666522342974351853233945241803369159786705715894207536149484923849028661574481467029705287777469404318289644381435066231436229667571818907503098196822458705545638853252664235026815826219815857665219510937559045319461514423963308375230255747627092664744423700515723287474035846085624585648157802777717624788324584637939281805690837627234749174654284087983532906000938834098877756285104848673145057290715987400113116357621033614332809542039066809038313061003036592012244039654526877555163837657446280390674602600494329607269004055933138419349447408505741859782006560892859787644824461001688595461115855616003323360332241635143031313606797822673489082412133995201568030082099841662429419818228747712437297613919837074498818259445880727260259069372902705722196669465789855409393009094881086538447485779294494203647752760219463740741507727885618521892241202200897699909428778835762307382366391487035942088455033153887118847708187923651341660769642122796649010012506966020437649203324738173151668835845547649633449564072733439725766005466805426727648706900288466500403612949652686222204939144408695224229059863139764400561730346147549836715571537641228371622113535541024276265947279892115814466520183722053628061126147840814558131104534672997870219203966914199306294826752904600109342942277933522964819392613887899059743948712483619515499244846870544363454079527265229519151028343120378448953681262237127110681908883308288358019212010655525807318434080671350998352370274928376596620668828504176198057358418773519444250698409763857445746448317572017042285566986728346991470028761839024156514128668067201068315640710395367885081367040576038215327808410986040341502361843139817010102031324175166429783835886749044538135020995288423320135692606636484978031902344842049864347432886833445078242224492701231675238570004123929414502900026556138203384026593777751699613655114347464071039531181510692757684730046231312372903897846056930255598529700594467970450842061071143662207834739614815929999618262963871870124039837492593191338028597264210928634885015068295423158857801599035303995087171057116777830701556292597064635232207207486622248902202045087671530461941335700457811751492768223684257463797850328194746604515975905150919986450934899496924779678843985810497978404914747517093709603072654868599034332719720297959913882411072867800535171317872071928091380482163608645058204485412505827227186444492663974856154037544897578013801222216925669134637315850802400757062540185663618283990874508348731676546236007755209822787596814884668762026762001253019092965565603773814392229152993903999153347646841849695582202871449523969352943350487199749382397473766550422288574470075042724651175342106958957848842421326477236820535550087875638930975728256332535072404476435192883611917344919571411381596302281132121575661437351324575537730713904371461062203318355897560164633992111436475854644077488480027258465990878173820317161999265366139112779575482868143888987388802546318533608622959702908406138313739646468030485458742353240154219625443717547204525311626487192521248274260405768535795669016645343506102359215929393556205773270539417100221289807821854702022004808745712990648712315084023684079751958378627366067055738485320004219421218738903950944920815798482365520217152586731769730663062868456758683736192950105916775731350772000502681587126321378573044106386356340947721500560464810356037914635377947142383380543291943315571094499487599129415120286080778804191609252582465535040305066331977495432876989306610245482728632898318159473042328572912348293282434883101479185340868688758532028506861583756747556124764013752137683953486508274867585273950979288040792050747108061893336246337894117270453179151546559327236856264004497227625857187435905995440776715283773055959053433325546104295268888134771439075500164126963787699265983392423171463025060777783437173919914842284821646368433284692361276558544674847529766795453700078983355974063144127022015577850599759499158101586856658275278001203380318373269376249065695151421486809098944701384115151824438593181771189031549096311802024697310876723454341086544487717649107166724338185483839676544527596921746945768842682344859709366279000798163742928088733041302974845121743345964626563097136913855931133412664215287138063749853469355472283035391556533032394758708424214409347396413517666805676206885300811601024837734915537918563260382427459095173499080657126322453771159018172612694859085051865841247503383968158424805076459498730605911017975492713484578016690241191879461125748765635862184020969463888237130802116383492411390937903171014408863056359387019899960989111094666137860963778749297169294496564832930732464186721810592957541649041082970288519620498166919024548299320197597507275288674432905873455042562948950571903786604684037251434824074745549385580314216733683403018881861011991221586913798559053041025064369933532696149882235155974996516541555999088331030705748042193682677264199128186215359685654118764641421965765951680995864055016770295133214688374388907501681767078950041808769023052087520612844386869278185681086147788673567484312968776211705219634264905805980837527750242626733163232328642966648309662774230207677861833552674054569782813732249724178514603855972322785223727455411301963978271427099430141868650392247782742825696241550246368297491476610760516725174632000899173862775524469162334913883250089653221191988664475116954159341510920413689185057658590976349918865776219186669506386853042048716894900935198286449529210428799656590998199405169525259624203311605987677923757690591654083842981549271673897818428246663108883469195666100647922503217759201855441480645496574587110060685396829257002235096987433739523062569430783043142330661290780416786189715498917140788350557413152812280307719689742887708279489997512582485169420704415930549376441957871654658460068579971560505164182051626763689852261171169685425982259194137047509394975258067754731184254715950096613490866844401330544397054554219726319458282697266738871374320859153567305368916928999102081016965684181399995351098547715171552273368447333469482200116555953201030439875104785143722673839583228849601876779690554012608777694884582445574280638948578803880696862481053127321796671287587899485654634619250412136567635461037144616610283616869891701705658033631614113206866176728445674874347078649501836068718915398017460418724656069752027151895914119337493070640191003383755232782998582353862554707797399899022054179064497600624409687682486005332103426842483648665092455957977634015089798980442275196115947422854789890689949621889347305585213223398200316926404343586645137317897079645129560053602706982608834313047580840022016476814043144259004734237802966938733824646521586983257612734771828732740156851806756754913464430245529841557342139939984894404789634162216454774978978967243528647952743373587804771966903490353248974085096587566177675970473591275576762297110834284879492737336514008889552200472355187561379873682081497243728149265843448306672850331675483418328457939808611654280370688625384470250881709384382485406657094822138007875500109783690534997149365850723087956006233792050770214443232904195970887616907840274798576509112114998552966622220250049895363715352097119893982937626492872843053215008922872641297933515352388372577405167162609079901516191659523446611010610718145055980017238372484201553296456618454212581269453370821773730768540728021020865479423737730712755527189040893444439874473547931882177632531061585157214186592200271740314078033979712359735521455349117211716539293696556955489833516455898953563719508325499965845813161602501175019916286058636373146707389050970745901932130344554313048129552695608525968997133801969650276171647109235691215282094132509605772405345886197010906677897257593891520250297907166451044256873075171730412957931184326174256758047466785489523873887603504343803779424435812093895790941381463316531043891944777028724702429129619934983199703897633502136136198516339884821290691280844051015739541974358042506947584435356041425656532801626937727635143804548353079017630613236131395203549839050348483265450318752145026605846813734618903971301746312656660326382332630418890708982738694415300595772494607774736157617433989340134500993029885675981017573393388942320527425892626160954637126296804385360258169316393107018061252493429379012296177148420751717192062757157279144146351825412432844822920854982274643161313183953704545321053670744900613325452071665442023887967795140829361353487279045017839108906935951080560102755084062678976305310838881165869921802995457079191517158656566502373286683014630049236621263567118502931602126591830689453992245671661326020958411478826090220378761406444390841532596616929904530681189440617778241775072714278027067812793717517408950548378758249934270157551030695089856110466893843239303156309884504368011588036142112353819037715307160651273510733404181019419725317910690571806305254875475121255797244926701174057734235011983610515882403136963992148266488517974686852397432461827383779937286115753611932818961659919920322449682994285318082734527044944951432343263643773582336181454236620381033922507933703409612896667991266514683729663857513717638557145651967689877433219166877455565274593936202607742949130066869702902020361027699921027362009513004780293284694505218874120216362901135531949038976660524634661884233542496488183451038480768393081292712274629197008247148266167378726969340078502862401184051610567866077307052810866432919590339203049023168529241713160680976203175755572582846623066114124999907986680268741787412049831452464178918622627030686336187084753021373739261716414917156058310903097673265626380810470930088924481341370081285502279226547996781201189953292800172225930937446083012451295985922978596899676965763496665338089142523166176495911663684569666472029322509511461763395601558158054542892437483543891470510921339977524477812604975178833289248857712594166544911477248995598250071843517220339613888547077929295850162146780464499838875659617111277492914267870088770067935140859257226088785571160247827677000096191207912657357297858639481487464364477778086947098285365940258576075306098354670457957069950510296954838240404988611656220282362240838657352908391510740175453384584588461090243881315534592246051692095143722954407477833003455097278436154587483909755151879753540833382915407292656867924206446193019641423368208016245128383595187510753378011532732388261921776186057280389453939800203520238750723773789578334858892289768176490915249897212469630210426352290156460817370645912638503934222717822264787912125633242554763525953200682364484945457996204962915536820242977643127533459062364741752696852500758720708976892495691772160993910615029261919214343324862024071171035815957729088394119971469773398618479055670221055074571633395884169219277415571156881492132304089700983187236463305249688370434536839402006798470414513609377450230878963293031329648473990971347187592022110965406735920990651759613677165536273262113018097434740077105641060395040435991399771060635884928427590824324538446123242781862346902406233897354429969987876065710871411186567699111463788875959173555389947379271919698049248540169207222694191275736770289254643029113776495381223797607533096358537728365131022543879322063673418193746356399990444791556746999292596464912760107106615363365988496145742670658583168730079723650260189572487395231249274247521974599226409583987519454424472128101565023029163642089197364066458843865944531890544722511865688053447100420815424347804483814469552609314055883087283287565925683178682321869342049552549901165636973740545009042736016591634952288918437628735416743736521605865540118445422155463032130862543257263112211016098276303315381159723845688851807351237812481413948967715617368475924840916670720164344063276818190688326996795293220441705200841852661603283118620822463764347767402346327180468514377286495228960657416039457987572129089592364759015373173631898337994405318169965157639288018576577523213019586190755430043555915830830214685383728359159982704898770040391488808161964193958872167819699026971582608297733589601352180223867813098950261182965210611328099534692851573365253810219767311521531256812798719227728710705316670702586441531961871948424764468638787313431914126045514008536611299177682083540702129172362242748849013792185929521111611810352621511200824174783085261359090729572546259617340369507643467693718858427031770102535904567120053666441245537386992170474158310460860531735195885652586025681553705363775159196100887692516388436315695634711838180287813952312202638446551710743659858674890038457197315166906228141157962820817698696093949444210439609823602382622955547529784382742401072990691612095990863237762726474966100154932232509549344587485716488429583841061533430368844969631179041979016704895804614983289284463056985196643213582077820297336517937583655921265221259064429270845402261786166131711479409918338419926125677471051098676563215391921920586339705242463798807523518216548904857173990997617540892704160647972119639940845304941875696204739369581009088248955016202490890319485558667725297878680021749067728361353300885374236107904392858268182615314317026191297515293879507239861270527402976763045111864359641311036315693947819788655410775634552468946453609284089450798028006446121304144683034534439547861986308572373415268322451871832031660859106954779415176344067566805067106301240639623234277239200472868428948702628593433650984162231350989763534972537590546155023337979996432998920373825911002509627471693828741746654896749521337707274280357390017732091265245100043413398031808675239414090052078728013275035599222923773339548245527519655780259710700015399961259239637408158675271472450542582362692766231243528191439790391412571395327890329555699380596384047612989824906866314732961776726441108303454801566438880140743825361035545195717495528993305003197258233160953262584289453031581061816368677941653829181356985289874512117954841253969539780128913432372325198243187929786810122637007498293951418304990471375897074161640342405454753746618755962011065231622997975275457880988397548587367979107779928541663760959569768176659786335180046702515521734367402343872470863448629760049560646201046491567989046355367097467185410551464145555793729181702003491030260446817526925709708696169189825563230529699762288672576535744073392284625580723105972364990442895324152763315886553222840809613548700209142258038271949037615061714857532773942565668957707929136062517473762902794546841568599181816975331866225230422834288538157958697912477773178189160910946303

[danbaron]

I don't know how Mathematica does it.

I am mostly ignorant.

The only thing I can think of is that, Mathematica is doing probabilistic primality testing, and is not testing for absolute certitude.

[Johannes]

Additionally, from the proof that the prime sequence is infinite, we know that if we multiply the sequence, 2, 3, 5, 7, etc., and stop anywhere we want, and then add 1 to the total, then that number is prime (I know I am not teaching you anything, Johannes).

For instance,
2 * 3 + 1 = 7, is prime.
2 * 3 * 5 + 1 = 31, is prime.
2 * 3 * 5 * 7 + 1 = 211, is prime.

Actually, I hadn't realised that particular one.

But even using the Sieve of Eratosthenes you can prove it. I have a complete list of all primes smaller than 65536 (a program to very quickly factor 32-bit values) and multiplying all those primes and adding one gives a gynormous prime.

Doing this for all primes up to 1,000,000 results in a prime of 433,637 digits. I've just started the script to see what the result is for primes up to 10 million...