Strong and weak primes: Difference between revisions

From Rosetta Code
Content added Content deleted
m (added a link to a Related task.)
(added Pascal)
Line 35: Line 35:
<br><br>
<br><br>


=={{header|Pascal}}==
Converting the primes into deltaPrime, so that its easy to check the strong/weakness.
Startprime 2 +1 -> (3)+2-> (5)+2 ->(7) +4-> (11)+2 .... 1,2,2,4,2,4,2,4,6,2,....
By using only odd primes startprime is 3 and delta -> delta/2
If deltaAfter<deltaBefore than a strong prime is found.
<lang pascal>program WeakPrim;
{$IFNDEF FPC}
{$AppType CONSOLE}
{$ENDIF}
const
PrimeLimit = 1000*1000*1000;//must be >= 2*3;
type
tLimit = 0..(PrimeLimit-1) DIV 2;
tPrimCnt = 0..51*1000*1000;
tWeakStrong = record
strong,
indifferent,
weak : NativeUint;
end;
var
primes: array [tLimit] of byte; //always initialized with 0 at startup
delta : array [tPrimCnt] of byte;
cntWS : tWeakStrong;
deltaCnt :NativeUint;
procedure sieveprimes;
//Only odd numbers, minimal count of strikes
var
spIdx,sieveprime,sievePos,fact :NativeUInt;
begin
spIdx := 1;
repeat
if primes[spIdx]=0 then
begin
sieveprime := 2*spIdx+1;
fact := PrimeLimit DIV sieveprime;
if Not(odd(fact)) then
dec(fact);
IF fact < sieveprime then
BREAK;
sievePos := ((fact*sieveprime)-1) DIV 2;
fact := (fact-1) DIV 2;
repeat
primes[sievePos] := 1;
repeat
dec(fact);
dec(sievePos,sieveprime);
until primes[fact]= 0;
until fact < spIdx;
end;
inc(spIdx);
until false;
end;
{ Not neccessary for this small primes.
procedure EmergencyStop(i:NativeInt);
Begin
Writeln( 'STOP at ',i,'.th prime');
HALT(i);
end;
}
function GetDeltas:NativeUint;
var
i,j,last : NativeInt;
Begin
j :=0;
i := 1;
last :=1;
For i := 1 to High(primes) do
if primes[i] = 0 then
Begin
//IF i-last > 255 {aka delta prim > 512} then EmergencyStop (j);
delta[j] := i-last;
last := i;
inc(j);
end;
GetDeltas := j;
end;
procedure OutHeader;
Begin
writeln('Limit':12,'Strong':10,'indifferent':12,'weak':10);
end;

procedure OutcntWS (const cntWS : tWeakStrong;Lmt:NativeInt);
Begin
with cntWS do
writeln(lmt:12,Strong:10,indifferent:12,weak:10);
end;

procedure CntWeakStrong10(var Out:tWeakStrong);
var
idx,diff,prime,lmt :NativeInt;
begin
OutHeader;
lmt := 10;
fillchar(Out,SizeOf(Out),#0);
idx := 0;
prime:=3;
repeat
dec(prime,2*delta[idx]);
while idx < deltaCnt do
Begin
inc(prime,2*delta[idx]);
IF prime > lmt then
BREAK;
diff := delta[idx] - delta[idx+1];
if diff>0 then
inc(Out.strong)
else
if diff< 0 then
inc(Out.weak)
else
inc(Out.indifferent);
inc(idx);
end;
OutcntWS(Out,Lmt);
lmt := lmt*10;
until Lmt > PrimeLimit;
end;

procedure WeakOut(cnt:NativeInt);
var
idx,prime : NativeInt;
begin
Writeln('The first ',cnt,' weak primes');
prime:=3;
idx := 0;
repeat
inc(prime,2*delta[idx]);
if delta[idx] - delta[idx+1]< 0 then
Begin
write(prime,' ');
dec(cnt);
IF cnt <=0 then
BREAK;
end;
inc(idx);
until idx >= deltaCnt;
Writeln;
end;

procedure StrongOut(cnt:NativeInt);
var
idx,prime : NativeInt;
begin
Writeln('The first ',cnt,' strong primes');
prime:=3;
idx := 0;
repeat
inc(prime,2*delta[idx]);
if delta[idx] - delta[idx+1]> 0 then
Begin
write(prime,' ');
dec(cnt);
IF cnt <=0 then
BREAK;
end;
inc(idx);
until idx >= deltaCnt;
Writeln;
end;

begin
sieveprimes;
deltaCnt := GetDeltas;
StrongOut(36);
WeakOut(37);
CntWeakStrong10(CntWs);
end.</lang>
{{Out}}
<pre>
The first 36 strong primes
11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439
The first 37 weak primes
3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401
Limit Strong indifferent weak
10 0 1 2
100 10 2 12
1000 73 15 79
10000 574 65 589
100000 4543 434 4614
1000000 37723 2994 37780
10000000 320991 21837 321750
100000000 2796946 167032 2797476
1000000000 24758535 1328401 24760597

real 0m3.011s</pre>
=={{header|REXX}}==
=={{header|REXX}}==
<lang rexx>/*REXX program lists a sequence (or a count) of ──strong── or ──weak── primes. */
<lang rexx>/*REXX program lists a sequence (or a count) of ──strong── or ──weak── primes. */

Revision as of 12:03, 3 December 2018

Strong and weak primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.


Definitions   (as per number theory)
  •   The   prime(p)   is the   pth   prime.
  •   prime(1)   is   2
  •   prime(4)   is   7
  •   A   strong   prime   is when     prime(p)   is   >   [prime(p-1) + prime(p+1)] ÷ 2
  •   A     weak   prime   is when     prime(p)   is   <   [prime(p-1) + prime(p+1)] ÷ 2


Note that the definition for   strong primes   is different when used in the context of   cryptography.


Task
  •   Find and display (on one line) the first   36   strong primes.
  •   Find and display the   count   of the strong primes below   1,000,000.
  •   Find and display the   count   of the strong primes below 10,000,000.
  •   Find and display (on one line) the first   37   weak primes.
  •   Find and display the   count   of the weak primes below   1,000,000.
  •   Find and display the   count   of the weak primes below 10,000,000.
  •   (Optional)   display the   counts   and   "below numbers"   with commas.

Show all output here.


Related Task


Also see



Pascal

Converting the primes into deltaPrime, so that its easy to check the strong/weakness. Startprime 2 +1 -> (3)+2-> (5)+2 ->(7) +4-> (11)+2 .... 1,2,2,4,2,4,2,4,6,2,.... By using only odd primes startprime is 3 and delta -> delta/2

If deltaAfter<deltaBefore than a strong prime is found. <lang pascal>program WeakPrim; {$IFNDEF FPC} 

 {$AppType CONSOLE}

{$ENDIF} const 

 PrimeLimit = 1000*1000*1000;//must be >= 2*3;

type 

 tLimit = 0..(PrimeLimit-1) DIV 2;
 tPrimCnt = 0..51*1000*1000;  
 tWeakStrong = record
                  strong,
                  indifferent,
                  weak : NativeUint;
               end;

var 

 primes: array [tLimit] of byte; //always initialized with 0 at startup
 delta : array [tPrimCnt] of byte;
 cntWS : tWeakStrong;  
 deltaCnt :NativeUint;

procedure sieveprimes; //Only odd numbers, minimal count of strikes var 

 spIdx,sieveprime,sievePos,fact :NativeUInt;

begin 

 spIdx := 1;
 repeat
   if primes[spIdx]=0 then
   begin
     sieveprime := 2*spIdx+1;
     fact := PrimeLimit DIV sieveprime;
     if Not(odd(fact)) then
       dec(fact);
     IF fact < sieveprime then
       BREAK;
     sievePos := ((fact*sieveprime)-1) DIV 2;
     fact := (fact-1) DIV 2;
     repeat
       primes[sievePos] := 1;
       repeat
         dec(fact);
         dec(sievePos,sieveprime);
       until primes[fact]= 0;
     until fact < spIdx;
   end;
   inc(spIdx);
 until false;

end; { Not neccessary for this small primes. procedure EmergencyStop(i:NativeInt); Begin 

 Writeln( 'STOP at ',i,'.th prime');
 HALT(i);

end; } function GetDeltas:NativeUint; var 

 i,j,last : NativeInt;

Begin 

 j :=0;
 i := 1;
 last :=1;
 For i := 1 to High(primes) do
   if primes[i] = 0 then
   Begin
     //IF i-last > 255 {aka delta prim > 512} then  EmergencyStop (j);
     delta[j] := i-last;
     last := i;
     inc(j);
  end;
  GetDeltas := j;

end;

procedure OutHeader; Begin 

 writeln('Limit':12,'Strong':10,'indifferent':12,'weak':10);

end;

procedure OutcntWS (const cntWS : tWeakStrong;Lmt:NativeInt); Begin 

 with cntWS do
   writeln(lmt:12,Strong:10,indifferent:12,weak:10);

end;

procedure CntWeakStrong10(var Out:tWeakStrong); var 

 idx,diff,prime,lmt :NativeInt;

begin 

 OutHeader;
 lmt := 10;
 fillchar(Out,SizeOf(Out),#0);
 idx := 0;
 prime:=3;
 repeat
   dec(prime,2*delta[idx]);  
   while idx < deltaCnt do   
   Begin
     inc(prime,2*delta[idx]);
     IF prime > lmt then 
        BREAK;
        
     diff := delta[idx] - delta[idx+1];
     if diff>0 then 
       inc(Out.strong)
     else  
       if diff< 0 then 
         inc(Out.weak)
       else
         inc(Out.indifferent);
         
     inc(idx);            
   end; 
   OutcntWS(Out,Lmt);
   lmt := lmt*10;
 until Lmt >  PrimeLimit;

end;

procedure WeakOut(cnt:NativeInt); var 

 idx,prime : NativeInt;

begin 

 Writeln('The first ',cnt,' weak primes');
 prime:=3;      
 idx := 0;
 repeat
   inc(prime,2*delta[idx]);  
   if delta[idx] - delta[idx+1]< 0 then
   Begin 
     write(prime,' ');
     dec(cnt);
     IF cnt <=0 then
       BREAK;
   end; 
   inc(idx);   
 until idx >= deltaCnt;
 Writeln;

end;

procedure StrongOut(cnt:NativeInt); var 

 idx,prime : NativeInt;

begin 

 Writeln('The first ',cnt,' strong primes');
 prime:=3;      
 idx := 0;
 repeat
   inc(prime,2*delta[idx]);  
   if delta[idx] - delta[idx+1]> 0 then
   Begin 
     write(prime,' ');
     dec(cnt);
     IF cnt <=0 then
       BREAK;
   end; 
   inc(idx);   
 until idx >= deltaCnt;
 Writeln;

end;

begin 

 sieveprimes;
 deltaCnt := GetDeltas;  
 
 StrongOut(36);
 WeakOut(37);
 CntWeakStrong10(CntWs);

end.</lang>

Output:
The first 36 strong primes
11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439 
The first 37 weak primes
3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 
       Limit    Strong indifferent      weak
          10         0           1         2
         100        10           2        12
        1000        73          15        79
       10000       574          65       589
      100000      4543         434      4614
     1000000     37723        2994     37780
    10000000    320991       21837    321750
   100000000   2796946      167032   2797476
  1000000000  24758535     1328401  24760597

real    0m3.011s

REXX

<lang rexx>/*REXX program lists a sequence (or a count) of ──strong── or ──weak── primes. */ parse arg N kind _ . 1 . okind; upper kind /*obtain optional arguments from the CL*/ if N== | N=="," then N= 36 /*Not specified? Then assume default.*/ if kind== | kind=="," then kind= 'STRONG' /* " " " " " */ if _\== then call ser 'too many arguments specified.' if kind\=='WEAK' & kind\=='STRONG' then call ser 'invalid 2nd argument: ' okind if kind =='WEAK' then weak= 1; else weak= 0 /*WEAK is a binary value for function.*/ w = linesize() - 1 /*obtain the usable 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;  !.9=23; #= 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=3 for #-2 while lim<=N /* [↓] find primes, and maybe show 'em*/ 

       call strongWeak i-1;       $= strip($)   /*go see if other part of a KIND prime.*/
       end   /*i*/                              /* [↑]  allows faster loop (below).    */
                                                /* [↓]  N:  default lists up to 35 #'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 strongWeak #-1                           /*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 & y>N then do; lim= y; m= m-1; end; else call app; return 1 app: if tell then if length($ y)>w then do; say $; $= y; end; else $= $ y; 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 _ /*──────────────────────────────────────────────────────────────────────────────────────*/ strongWeak: parse arg x; Lp= x - 1; Hp= x + 1; y=!.x; s= (!.Lp + !.Hp) / 2 

           if weak  then if ys  then return add()               /*is  an strong prime.*/
                                      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 default input of:     36   strong 
11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439

36  STRONG primes found.
output   when using the default input of:     -1000000   strong 
37,723  STRONG primes found below or equal to  1,000,000.
output   when using the default input of:     -10000000   strong 
320,991  STRONG primes found below or equal to  10,000,000.
output   when using the default input of:     37   weak 
3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401

37  WEAK primes found.
output   when using the default input of:     -1000000   weak 
37,780  WEAK primes found below or equal to  1,000,000.
output   when using the default input of:     -1000000   weak 
321,750  WEAK primes found below or equal to  10,000,000.
Retrieved from "https://rosettacode.org/wiki/Strong_and_weak_primes?oldid=286654"