Figure 1:The Sieve of Eratosthenes. It is a methodical procedure for finding prime numbers, originally using a table. Notice that factors are eliminated only up to and including that which exceeds the square root of 120 (= 11). (Graphic by SKopp at German Wikipedia
.
This module implements the Sieve of Eratosthenes method for the listing of prime numbers. It is made to run in Microsoft Excel as a standard VBA module. It lists the prime numbers found between unity and some parameter integer value, on Sheet1 of the Workbook, and makes use of a message box for short listings.
Overflow is a problem for such procedures, but provided that the input parameter is kept within a few millions or so, overflow is unlikely.
The method although simple is quite slow, since even to test one single value, the entire sequence of multiples (2,3,5,7,...n) must be completed. Large values of input will take several minutes to complete. A faster approach is to test only those factors that are smaller than the square root of the input value; this modification is used in the procedure GetPrimeFactors().
Note that the procedure will clear any contents of Sheet1 before each listing.
An animated GIF found in Wiki Commons is included in Figure 1 to illustrate the method.
GetPrimeFactors() and its utility DecMod() list the prime factors of a supplied integer. It is written for the decimal subtype, and so it handles inputs of up to 28 full digits, (assuming all nines). The time to complete varies greatly, depending on how many primes are found. There is one peculiarity noted; for example, with an input of 23 nines the answer takes a very long time, but for 28 nines it takes just fifteen seconds or so. Other values like 20, 21, and 22 nines, and so on, are virtually instantaneous. The use of a string for input in the test procedure testGetPrimeFactors() is simply to prevent Excel from truncating the displayed input integer, and has no bearing on the method used; it is not string math here; just a decimal subtype loop.
OptionExplicitSubtestListPrimes()'Run this to list primes in range of'unity to some integer valueDimnNumAsLong'set upper limit of range here'eg:1234567 gives 95360 primes from 2 to 1234547 in 3 minutesnNum=1234567'MsgBox ListPrimes(nNum)ListPrimesnNumEndSubFunctionListPrimes(nInputAsLong)AsString'Lists primes in range unity to nInput'Output to Sheet1 and function name'Method: Sieve of EratosthenesDimarr()AsLong,oShtAsWorksheet,sOutAsStringDimaAsLong,bAsLong,cAsLong,sAsLongDimnRowAsLong,nColAsLong'dimension arrayReDimarr(1TonInput)'set reference to Sheet1SetoSht=ThisWorkbook.Worksheets("Sheet1")WithoSht.Activate.Cells.ClearContentsEndWith'fill work array with integersIfnInput>1Thenarr(1)=0'exception first elementFora=2TonInputarr(a)=aNextaElseMsgBox"Needs parameter greater than unity - closing"ExitFunctionEndIf'Sieve of Eratosthenes'progressively eliminate prime multiplesForb=2TonInputDoEvents'yieldIfarr(b)<>0Then'skip zeroed items'replace prime multiples with zeros=2*bDoUntils>nInputDoEvents'yieldarr(s)=0s=s+bLoopEndIfNextb'Output of primessOut="Primes in range 1 to "&nInput&":"&vbCrLfnRow=1:nCol=1Forc=2TonInputIfarr(c)<>0ThenoSht.Cells(nRow,nCol)=c'primes list to Sheet1nRow=nRow+1Ifc<>nInputThen'and accumulate a stringsOut=sOut&c&","ElsesOut=sOut&cEndIfEndIfNextcListPrimes=sOutEndFunctionSubtestGetPrimeFactors()'Run this for prime factors of integer'Set integer as a string in sIn to avoid display truncation'Decimal subtype applies and limited to 28 full digits.DimnIn,sInAsString,Reply,sOutAsString,sTAsString'set integer to factorise here, as a stringsIn="9999999999999999999999999999"'28 nines takes 15 secondsnIn=CDec(sIn)sOut=GetPrimeFactors(nIn)MsgBoxsOut&vbCrLf&_
"Input digits length : "&Len(sIn)'optional inputbox allows copy of outputReply=InputBox("Factors of"&nIn,,sOut)EndSubFunctionDecMod(DividendAsVariant,DivisorAsVariant)AsVariant' Declare two double precision variablesDimD1AsVariant,D2AsVariantD1=CDec(Dividend)D2=CDec(Divisor)'return remainder after divisionDecMod=D1-(Int(D1/D2)*D2)EndFunctionFunctionGetPrimeFactors(ByValnNAsVariant)AsString'Returns prime factors of nN in parameter'Maximum of 28 digits full digits for decimal subtype input.'Completion times vary greatly - faster for more primes'20,21,and 22 nines factorise immediately, 23 nines time excessive.'25 nines in 6 seconds. Maximum input takes 15 seconds for 28 nines.DimnPAsVariant,sAccAsStringnP=CDec(nP)nP=2nN=CDec(nN)sAcc=nN&" = "'test successive factorsDoWhilenN>=nP*nPDoEventsIfDecMod(nN,nP)=0ThensAcc=sAcc&nP&" * "nN=nN/nP'(divide by prime)ElsenP=nP+1EndIfLoop'output resultsGetPrimeFactors=sAcc&CStr(nN)EndFunction