Anonymous user
Strong and weak primes: Difference between revisions
added Pascal
m (added a link to a Related task.) |
(added Pascal) |
||
Line 35:
<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}}==
<lang rexx>/*REXX program lists a sequence (or a count) of ──strong── or ──weak── primes. */
| |||