Sequence of primes by trial division: Difference between revisions
Content added Content deleted
(→bc: add) |
(Added PL/I-80 example) |
||
Line 2,437: | Line 2,437: | ||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 |
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 |
||
The 10,001st prime is 104,743 |
The 10,001st prime is 104,743 |
||
</pre> |
|||
=={{header|PL/I-80}}== |
|||
<syntaxhighlight lang="PL/I"> |
|||
/* Prime Number Generator in PLI-80 |
|||
* |
|||
* The logic closely follows an example program by Edsger |
|||
* W. Dijkstra in his classic 1969 paper, "Notes on Structured |
|||
* Programming." Only odd numbers are checked for primality, |
|||
* and only the prime numbers previously found (up to the |
|||
* square root of the number under examination) are tested |
|||
* as divisors. |
|||
*/ |
|||
primes: |
|||
proc options (main); |
|||
%replace |
|||
maxprimes by 3500, /* practical limit before overflow */ |
|||
false by '0'b, |
|||
true by '1'b; |
|||
dcl |
|||
p(1:maxprimes) fixed binary(15), |
|||
divisible bit(1), |
|||
dummy char(1), |
|||
(i, k, m, n, s, nprimes, divisor) fixed binary(15); |
|||
put skip list ('How many primes do you want? '); |
|||
get list (nprimes); |
|||
if nprimes > maxprimes then |
|||
do; |
|||
nprimes = maxprimes; |
|||
put skip list ('Only generating',maxprimes,' primes.'); |
|||
put skip list ('Press CR to continue.'); |
|||
get edit (dummy) (a); |
|||
end; |
|||
/* initialize p with first prime number and display it */ |
|||
p(1) = 2; |
|||
put skip list (p(1)); |
|||
i = 1; /* count of prime numbers found so far */ |
|||
k = 1; /* index of largest prime <= sqrt of n */ |
|||
n = 3; /* current number being checked */ |
|||
do while (i < nprimes); |
|||
s = p(k) * p(k); |
|||
if s <= n then k = k + 1; |
|||
divisible = false; |
|||
m = 1; /* index into primes already found */ |
|||
do while ((m <= k) & (divisible = false)); |
|||
divisor = p(m); /* can't put p(m) directly into mod()! */ |
|||
if mod(n, divisor) = 0 then divisible = true; |
|||
m = m + 1; |
|||
end; |
|||
if divisible = false then /* found a prime */ |
|||
do; |
|||
i = i + 1; |
|||
p(i) = n; |
|||
put list (n); |
|||
end; |
|||
n = n + 2; /* advance to next odd number */ |
|||
end; |
|||
put skip list ('All done. Goodbye.'); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
How many primes do you want? 100 |
|||
2 3 5 7 11 13 17 19 |
|||
23 29 31 37 41 43 47 53 |
|||
59 61 67 71 73 79 83 89 |
|||
* * * |
|||
419 421 431 433 439 443 449 457 |
|||
461 463 467 479 487 491 499 503 |
|||
509 521 523 541 |
|||
All done. Goodbye. |
|||
</pre> |
</pre> |
||