Safe primes and unsafe primes
Show all output here.
- Definitions
-
- A safe prime is a prime p and where (p-1)/2 is also prime.
- The corresponding prime (p-1)/2 is known as a Sophie Germain prime.
- An unsafe prime is a prime p and where (p-1)/2 isn't a prime.
- An unsafe prime is a prime that isn't a safe prime.
- Task
-
- Find and display (on one line) the first 35 safe primes.
- Find and display the count of the safe primes below 1,000,000.
- Find and display the count of the safe primes below 10,000,000.
- Find and display (on one line) the first 40 unsafe primes.
- Find and display the count of the unsafe primes below 1,000,000.
- Find and display the count of the unsafe primes below 10,000,000.
- (Optional) display the counts and "below numbers" with commas.
- Also see
-
- The OEIS article: safe primes.
- The OEIS article: unsafe primes.
REXX
<lang rexx>/*REXX program lists a sequence of primes by testing primality by trial division. */ parse arg N kind _ . 1 . okind; upper kind /*obtain optional arguments from the CL*/ if N== | N=="," then N= 26 /*Not specified? Then assume default.*/ if kind== | kind=="," then kind= 'SAFE' /* " " " " " */ if _\== then call ser 'too many arguments specified.' if kind\=='SAFE' & kind\=='UNSAFE' then call ser 'invalid 2nd argument: ' okind if kind =='UNSAFE' then safe= 0; else safe= 1 /*SAFE is a binary value for function.*/ w = linesize() - 1 /*obtain the useable width of the term.*/ tell= (N>0); @.=; N= abs(N) /*N is negative? Then don't display. */ !.=0; !.1=2; !.2=3; !.3=5; !.4=7; !.5=11; !.6=13; !.7=17; !.8=19; #= 8; @.=; @.2=1; @.3=1; @.5=1; @.7=1; @.11=1; @.13=1; @.17=1; @.19=1; start= # + 1 m= 0; lim=0 /*# is the number of low primes so far*/ $=; do i=1 for # while lim<=N; j= !.i /* [↓] find primes, and maybe show 'em*/
call safeUnsafe; $= strip($) /*go see if other part of a KIND prime.*/
end /*i*/ /* [↑] allows faster loop (below). */
/* [↓] N: default lists up to 101 #s.*/
do j=!.#+2 by 2 while lim<N /*continue on with the next odd prime. */
if j // 3 == 0 then iterate /*is this integer a multiple of three? */
parse var j -1 _ /*obtain the last decimal digit of J */
if _ == 5 then iterate /*is this integer a multiple of five? */
if j // 7 == 0 then iterate /* " " " " " " seven? */
if j //11 == 0 then iterate /* " " " " " " eleven?*/
if j //13 == 0 then iterate /* " " " " " " 13 ? */
if j //17 == 0 then iterate /* " " " " " " 17 ? */
if j //19 == 0 then iterate /* " " " " " " 19 ? */
/* [↓] divide by the primes. ___ */
do k=start to # while !.k * !.k<=j /*divide J by other primes ≤ √ J */
if j // !.k ==0 then iterate j /*÷ by prev. prime? ¬prime ___ */
end /*k*/ /* [↑] only divide up to √ J */
#= # + 1 /*bump the count of number of primes. */
!.#= j; @.j= 1 /*define a prime and its index value.*/
call safeUnsafe /*go see if other part of a KIND prime.*/
end /*j*/
/* [↓] display number of primes found.*/
if $\== then say $ /*display any residual primes in $ list*/ say if tell then say commas(m)' ' kind "primes found."
else say commas(m)' ' kind "primes found below or equal to " commas(N).
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ add: m= m+1; lim= m; if \tell & j>N then do; lim= j; m= m-1; end; else call app; return 1 app: if tell then if length($ j)>w then do; say $; $ =j; end; else $= $ j; return 1 ser: say; say; say '***error***' arg(1); say; say; exit 13 /*tell error message. */ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ safeUnsafe: ?= (j-1) % 2 /*obtain the other part of KIND prime. */
if safe then if @.? == then return 0 /*not a safe prime.*/
else return add() /*is " " " */
else if @.? == then return add() /*is an unsafe prime.*/
else return 0 /*not " " " */</lang>
This REXX program makes use of LINESIZE REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console). Some REXXes don't have this BIF.
The LINESIZE.REX REXX program is included here ───► LINESIZE.REX.
- output when using the input: 35
(output shown at 3/4 size.
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619 35 SAFE primes found.
- output when using the input: 1000000
30,657 SAFE primes found below or equal to 1,000,000.
- output when using the input: 10000000
633,922 SAFE primes found below or equal to 10,000,000.
- output when using the input: 40 unsafe
(output shown at 3/4 size.
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233 40 UNSAFE primes found.
- output when using the input: 1000000 unsafe
4,324 SAFE primes found below or equal to 1,000,000.
- output when using the input: 10000000 unsafe
74,174 SAFE primes found below or equal to 10,000,000.