## Παρασκευή, 13 Οκτωβρίου 2017

### Prime Numbers "Basic" style.

We can use numbers and old fashion programming for experiments, in M2000.

01 clear : flush   \\ clear variables and flush stack for values
02 data 100 \\ put 100 as last item in stack, but stack is empty so is first too
03 \\ if we ommit 02 data 100 we can call this module (say A) as A 100
04 \\ so  before A run, 100 get to top of stack (first to read)
10 read A \\ read  first argument from a module call or a Data before
20 print "Prime numbers"
30 print " ";
40 for x = 1 to A
50 gosub 1000
60 if p == 1 then print x;" ";
70 next x
80 print
90 end
1000 rem ** subroutine to check for prime **
1010 rem number to be checked is stored in x
1020 rem d is used for divisor
1030 rem q is used for quotient
1040 rem p is used for return value, if x is prime, p will be 1, else 0
1050 p = 0
1060 if x < 2 OR x <> int(x) then 1180
1070 if x == 2 OR x == 3 OR x == 5 then p=1 : goto 1180
1080 if x/2 == int(x/2) then 1180
1090 if x/3 == int(x/3) then 1180
1100 d = 5
1110 q = x/d : if q == int(q) then 1180
1120 d = d + 2
1130 if d*d> x then 1170
1140 q = x/d : if q == int(q) then 1180
1150 d = d + 4
1160 if d*d <= x then 1110
1170 p = 1
1180 return
1190 rem ** end of subroutine to check for prime **

We can make some modifications...using M2000 goods..

20 print "Prime numbers"
40 for x = 1 to A
50 gosub 1000
60 if p == 1 then print x,
70 next x
80 print
90 end
1000 rem ** subroutine to check for prime **
1010 rem number to be checked is stored in x
1020 rem d is used for divisor
1030 rem q is used for quotient
1040 rem p is used for return value, if x is prime, p will be 1, else 0
1050 p = 0
1060 if x < 2 OR x <> int(x) then return
1070 if x == 2 OR x == 3 OR x == 5 then p=1 : return
1080 if x/2 == int(x/2) then return
1090 if x/3 == int(x/3) then return
1100 d = 5
1101 {
1110 q = x/d : if q == int(q) then exit
1120 d = d + 2
1130 if d*d> x then p=1 : exit
1140 q = x/d : if q == int(q) then exit
1150 d = d + 4
1160 if d*d <= x then restart
1161 p = 1
1162 }
1180 return
1190 rem ** end of subroutine to check for prime **

Or we can be better

Function IsPrime (x) {
\\      if x < 2  then exit

if x<=5 OR frac(x) then {

if x == 2 OR x == 3 OR x == 5 then =True

Break
}

if frac(x/2 ) Else exit

if frac(x/3) Else exit

d = 5
{

q = x/d : if q == int(q) then exit

d = d + 2: if d*d> x then =True : exit

q = x/d : if q == int(q) then exit

d = d + 4: if d*d <= x then restart
= True
}

}
Print "Prime numbers"
for x = 2 to A {
if isPrime(x) then print x,
}
Print
End
Or more faster

Function IsPrime (x) {
if x<=5 OR frac(x) then {
if x == 2 OR x == 3 OR x == 5 then =true
Break
}
if frac(x/2 ) else exit
if frac(x/3) else exit
x1=sqrt(x):d = 5
{    if frac(x/d ) else exit
d += 2: if d>x1 then =true : exit
if frac(x/d) else exit
d += 4: if d<= x1 else =true: exit
loop
}
}
\\Print "Prime numbers"
i=0
for x = 2 to A {
if isPrime(x) then Print x, : i++
}
Print
Print i
End

So now we can use it for finding primes in a range of numbers.

form 80,32
print \$(,15)
Function IsPrime (x) {
if x<=5 OR frac(x) then {
if x == 2 OR x == 3 OR x == 5 then =true
Break
}
if frac(x/2 ) else exit
if frac(x/3) else exit
x1=sqrt(x):d = 5
{    if frac(x/d ) else exit
d += 2: if d>x1 then =true : exit
if frac(x/d) else exit
d += 4: if d<= x1 else =true: exit
loop
}
}
Print "Prime numbers"
i=0
M=12515000000
for x = 92355001+M to 92355499+M step 2 {
if isPrime(x) then Print x, : i++
}
Print
Print i
End

And this Euler's Sieve (much faster, but need to find all prime numbers..from start). If we copy to module A, then A 100, 1 find and display primes from 2 to 100. Using match("N") we check if top item in stack is a number and we create T with this value (read pop from stack).  We don't need a particular number, so we check if T exist using Valid(T)

\\ Euler's Sieve
if x>200000 then exit
Dim r(x+1)=1
k=2
k2=k**2
While k2<x {
For m=k2 to x step k {
r(m)=0
}
Repeat {
k++
k2=k**2
} Until r(k)=1 or k2>x
}
if not Valid(T) then exit
k=0
For i=2 to x {
if r(i)<>0 then print i, : k++
}
print
print k