Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
→{{header|Quackery}}: isprime now returns false if passed an argument larger than that passed to eratosthenes |
|||
Line 13,275: | Line 13,275: | ||
46 primes found up to and including 200 |
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> |
</pre> |
||