Code: Select all

```
'#cmdline "-exx"
'==============================================
'The following scheme is used for the sieve.
'It has the advantage that it determines the largest and smallest divisor for each odd number.
'The smallest divisor is prime, so that only the largest divisor needs to be broken down further.
' 3*3
' 5*3-> 5*5
' 7*3-> 7*5-> 7*7
' 9*3-> 9*5-> 9*7-> 9*9
'11*3->11*5->11*7->11*9->11*11
'13*3->13*5->13*7->13*9->13*11->13*13
'15*3->15*5->15*7->15*9->15*11->15*13->15*15
'Example for 45: First 9*5 is written, then overwritten with 15*3.
'For the 15 one finds 5*3.
'For the 5 one finds 0. An unmarked odd number is prime, therefore 45=3*3*5.
'The memory requirement could be reduced by half, but I have not done this for the sake of clarity.
'==============================================
dim shared as ulong limit = 15485863
dim shared as ulong a(1 to limit),b(1 to limit)
dim as ulong i
'==============================================
declare sub Sieve
declare sub TestArray
declare sub GetPrimes(lim as ulong = limit)
declare function GetPrimeFactors(number as ulong) as string
declare sub SavePrimeFactorList(n1 as ulong, n2 as ulong)
declare sub SavePrimeList
'==============================================
print "Please wait a few seconds..."
Sieve
cls
TestArray
for i = 3 to 45 step 2
print i,a(i),b(i)
next i
print "Any key to continue..." : sleep
print "Prime numbers below 100:"
GetPrimes(100)
print "Any key to continue..." : sleep
for i = limit-100 to limit
print GetPrimeFactors(i)
next i
'SavePrimeList : print "FirstMillionPrimes.txt is stored in ";exepath
'SavePrimeFactorList(2,100000) : print "PrimeFactorList.txt is stored in ";exepath
print "Any key to end..." : sleep
'==============================================
sub Sieve
dim as ulong i,j,k
for i = 3 to limit step 2
for j = 3 to i step 2
k = i * j
if k > limit then exit for
a(k) = i
b(k) = j
next
next
end sub
sub TestArray
dim as boolean ok = true
dim as ulong i
for i = 1 to limit
if b(i) > 0 then
if a(b(i)) > 0 then ok = false : print "b(";i;") is not prime" : sleep
end if
next i
if ok = true then print "Array b() OK!"
end sub
sub GetPrimes(lim as ulong = limit)
dim as ulong i
print 2u
for i = 3 to lim step 2
if a(i) = 0 then print i
next i
end sub
function GetPrimeFactors(number as ulong) as string
if (number = 0) or (number = 1) then return str(number) & " = ?"
dim as string s1,s2
dim as ulong n = number
dim as ubyte e2
while (n mod 2) = 0
n \= 2
e2 += 1
wend
if e2 > 0 then s1 = "(2^" & e2 & ")"
if n > 1 then
while b(n) > 0
s2 &= (b(n) & "*")
n = a(n)
wend
s2 &= n
end if
if (len(s1) > 0) and (len(s2) > 0) then s1 &= "*"
return str(number) & " = " & s1 & s2
end function
sub SavePrimeFactorList(n1 as ulong, n2 as ulong)
open "PrimeFactorList.txt" for output as #1
dim as ulong n
for n = n1 to n2
print #1,GetPrimeFactors(n)
next n
close #1
end sub
sub SavePrimeList
open "FirstMillionPrimes.txt" for output as #1
dim as ulong i
print #1,2u;
for i = 3 to limit step 2
if a(i) = 0 then
print #1,
print #1,i;
end if
next i
close #1
end sub
```