Sieve of Eratosthenes: Difference between revisions
→{{header|ooRexx}}
(→{{header|Quackery}}: isprime now returns false if passed an argument larger than that passed to eratosthenes) |
|||
Line 13,275:
46 primes found up to and including 200
</pre>
===Wheel Version===
<syntaxhighlight lang="oorexx">
/*ooRexx program generates primes via sieve of Eratosthenes algorithm.
* wheel version, 2 handled as special case
* loops optimized: outer loop stops at the square root of
* the limit, inner loop starts at the square of the
* prime just found
* use a list rather than an array and remove composites
* rather than just mark them
* convert list of primes to a list of output messages and
* display them with one say statement
*******************************************************************************/
arg highest -- get highest number to use.
if \highest~datatype('W') then
highest = 200 -- use default value.
w = highest~length -- width of the biggest number,
-- it's used for aligned output.
thePrimes = .list~of(2) -- the first prime is 2.
loop j = 3 to highest by 2 -- populate the list with odd nums.
thePrimes~append(j)
end
j = 3 -- first prime (other than 2)
ix = thePrimes~index(j) -- get the index of 3 in the list.
loop while j*j <= highest -- strike multiples of odd ints.
-- up to sqrt(highest).
loop jm = j*j to highest by j+j -- start at J squared, incr. by 2*J.
thePrimes~removeItem(jm) -- delete it since it's composite.
end
ix = thePrimes~next(ix) -- the index of the next prime.
j = thePrimes[ix] -- the next prime.
end
np = thePrimes~items -- the number of primes since the
-- list is now only primes.
out1 = ' prime number' -- first part of output messages.
out2 = ' --> ' -- middle part of output messages.
ix = thePrimes~first
loop n = 1 to np -- change the list of primes
-- to output messages.
thePrimes[ix] = out1 n~right(w) out2 thePrimes[ix]~right(w)
ix = thePrimes~next(ix)
end
last = np~right(out1~length+1+w) 'primes found up to and including ' highest
thePrimes~append(.endofline || last) -- add blank line and summary line.
say thePrimes~makearray~toString -- display the output.
exit
</syntaxhighlight>
{{out}}when using the limit of 100
<pre>
prime number 1 --> 2
prime number 2 --> 3
prime number 3 --> 5
prime number 4 --> 7
prime number 5 --> 11
prime number 6 --> 13
prime number 7 --> 17
prime number 8 --> 19
prime number 9 --> 23
prime number 10 --> 29
prime number 11 --> 31
prime number 12 --> 37
prime number 13 --> 41
prime number 14 --> 43
prime number 15 --> 47
prime number 16 --> 53
prime number 17 --> 59
prime number 18 --> 61
prime number 19 --> 67
prime number 20 --> 71
prime number 21 --> 73
prime number 22 --> 79
prime number 23 --> 83
prime number 24 --> 89
prime number 25 --> 97
25 primes found up to and including 100
</pre>
| |||