Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
m 2 small changes to program (don't affect result); trivial change to header |
|||
Line 1,702: | Line 1,702: | ||
====using 'easy way' to 'add' 2n wheels==== |
====using 'easy way' to 'add' 2n wheels==== |
||
{{trans|ZX Spectrum Basic}} |
{{trans|ZX Spectrum Basic}} |
||
Sets h$ to 1 for higher multiples of 2 via <code>FILL$</code>, later on |
Sets h$ to 1 for higher multiples of 2 via <code>FILL$</code>, later on sets <code>STEP</code> to 2n; replaces Floating Pt array p(z) with string variable h$(z) to sieve out all primes < z=441 (<code>l</code>=21) in under 1K, so that h$ is fillable to its maximum (32766), even on a 48K ZX Spectrum if translated back. |
||
<lang qbasic> |
<lang qbasic> |
||
10 INPUT "Enter Stopping Pt for squared factors: ";z |
10 INPUT "Enter Stopping Pt for squared factors: ";z |
||
15 LET l=SQR(z) |
15 LET l=SQR(z) |
||
20 LET h$="10" : h$=h$ & FILL$("01",z) |
20 LET h$="10" : h$=h$ & FILL$("01",z) |
||
40 FOR n=3 TO l |
40 FOR n=3 TO l |
||
50 IF h$(n) THEN NEXT n |
50 IF h$(n) THEN NEXT n |
||
60 FOR k=n*n TO z STEP n+n: h$(k)=1 |
60 FOR k=n*n TO z STEP n+n: h$(k)=1 |
||
Line 1,770: | Line 1,770: | ||
====Eulerian optimisation==== |
====Eulerian optimisation==== |
||
While slower than the optimised Sieve of Eratosthenes before it, the Sieve of Sundaram above has a compatible compression scheme that's more convenient than the conventional one used beforehand. It is therefore applied below along with Euler's alternative optimisation in a reversed implementation that lacks backward-compatibility to ZX80 BASIC. |
While slower than the optimised Sieve of Eratosthenes before it, the Sieve of Sundaram above has a compatible compression scheme that's more convenient than the conventional one used beforehand. It is therefore applied below along with Euler's alternative optimisation in a reversed implementation that lacks backward-compatibility to ZX80 BASIC. This program is designed around features & limitations of the QL, yet can be rewritten more efficiently for 1K ZX80s, as they allow integer variables to be parameters of <code>FOR</code> statements (& as their 1K of static RAM is equivalent to L1 cache, even in <code>FAST</code> mode). That's left as an exercise for ZX80 enthusiasts, who for o%=14 should be able to generate all primes < 841, i.e. 3 orders of (base 2) magnitude above the limit for the program listed under Sinclair ZX81 BASIC. In QL SuperBASIC, o% may at most be 127--generating all primes < 65,025 (almost 2x the upper limit for indices & integer variables used to calculate them ~2x faster than for floating point as used in line 30). |
||
<lang qbasic> |
<lang qbasic> |
||
10 INPUT "Enter highest value of |
10 INPUT "Enter highest value of diagonal index q%: ";o% |
||
15 LET z%=o%*(2+o%*2) : h$=FILL$("00",z%) : q%=1 : q=q% : m=z% DIV (2*q%+1) |
15 LET z%=o%*(2+o%*2) : h$=FILL$("00",z%) : q%=1 : q=q% : m=z% DIV (2*q%+1) |
||
30 FOR p=m TO q STEP -1: h$(p+q+2*q*p)="1" |
30 FOR p=m TO q STEP -1: h$(p+q+2*q*p)="1" |