Sequence of primes by trial division: Difference between revisions
Sequence of primes by trial division (view source)
Revision as of 23:41, 14 February 2023
, 1 year agoAdded PL/I-80 example
(→bc: add) |
(Added PL/I-80 example) |
||
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
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>
| |||