Anonymous user
Primes whose sum of digits is 25: Difference between revisions
→{{header|Pascal}}: reduced count of generated numbers for testing,move 1,3,7,9 and permute digits in front
(Realize in F#) |
(→{{header|Pascal}}: reduced count of generated numbers for testing,move 1,3,7,9 and permute digits in front) |
||
Line 1,055:
=={{header|Pascal}}==
added only strechted goal.Generating the combination of the digits for the numbers and afterwards generating the [[Permutations with some identical elements]]<BR>
Now seting one digit out of 1,3,7,9 to the end and permute the rest of the digits in front.<BR>So much less numbers have to be tested.10.5e6 instead of 16.4e6.Generating of the numbers is reduced in the same ratio.
<lang pascal>program Perm5aus8;
//formerly roborally take 5 cards out of 8
Line 1,071 ⟶ 1,069:
gmp;
const
cTotalSum =
cMaxCardsOnDeck = cTotalSum;//8
Line 1,083 ⟶ 1,081:
tSetElem = record
Elem : tDiffCardCount;
Elemcount : tDeckIndex;
tSet = record
RemSet : array [low(tDiffCardCount)..High(tDiffCardCount)] of tSetElem;
MaxUsedIdx,
TotElemCnt :
end;
tRemainSet = array [low(tSequenceIndex)..High(tSequenceIndex)+1] of tSet;
tCardSequence = array [low(tSequenceIndex)..High(tSequenceIndex)] of tDiffCardCount;
var
ManifoldOfDigit : array[tDiffCardCount] of Byte;
TotalUsedDigits : array[tDeckIndex] of Byte;
RemainSets : tRemainSet;
CardString : AnsiString;
PrimeCount : integer;
PermCount : integer;
//*****************************************************************************
var
CS : pchar;
z : mpz_t;
procedure SetInit(var ioSet:tSet);
var
i : integer;
begin
with
begin
MaxUsedIdx := 0;
Line 1,129 ⟶ 1,126:
end;
procedure CheckPrime
begin
mpz_set_str(z,CS,10);
inc(PrimeCount,ORD(mpz_probab_prime_p(z,3)>0));
end;
procedure Permute(depth,MaxCardsUsed:NativeInt);
var
i : NativeInt;
begin
i := 0;
repeat
if
//take one of the same elements of the stack
//insert in result here string
CS[depth] := chr(pSetElem^.Elem+Ord('0'));
//done one permutation
IF depth = MaxCardsUsed then
begin
inc(permCount);
end
else
begin
dec(pSetElem^.ElemCount);
RemainSets[depth+1]:= RemainSets[depth];
Permute(depth+1,MaxCardsUsed);
//re-insert that element
inc(
end;
end;
//move on to the next digit
inc(
inc(i);
until i >=RemainSets[depth].MaxUsedIdx;
Line 1,208 ⟶ 1,191:
TotElemCnt := dgtCnt;
MaxUsedIdx := dgtIdx;
CS := @CardString[1];
//Check only useful end-digits
For i := 0 to dgtIdx-1 do
Begin
if RemSet[i].Elem in[1,3,7,9]then
Begin
CS[dgtCnt-1] := chr(RemSet[i].Elem+Ord('0'));
CS[dgtCnt] := #00;
dec(RemSet[i].ElemCount);
permute(0,dgtCnt-2);
inc(RemSet[i].ElemCount);
end;
end;
end;
end;
Line 1,226 ⟶ 1,222:
Begin
Check(n);
//n is 0 based
inc(TotalUsedDigits[n+1]);
end;
Line 1,237 ⟶ 1,233:
i :NativeInt;
begin
setlength(CardString,SumGoal);
IF sumGoal>cTotalSum then
EXIT;
fillchar(ManifoldOfDigit[0],SizeOf(ManifoldOfDigit),#0);
PrimeCount := 0;
For i := 1 to 9 do
AppendToSum(0,i,SumGoal-i);
writeln('PrimeCount of generated numbers with digits sum of ',SumGoal,' are ',permcount);
writeln('Propably primes ',PrimeCount);
writeln;
end;
var
SumGoal: NativeInt;
BEGIN
writeln('GMP-Version ',gmp.version);
T0 := GetTickCount64;
For SumGoal := 25 to 25 do
Begin
CheckAll(SumGoal);
T1 := GetTickCount64;Writeln((T1-T0)/1000:7:3,' s');
T0 := T1;
end;
mpz_clear(z);
END.
</lang>
{{out}}
<pre>
//Runnning on TIO.RUN
GMP-Version 6.1.2
PrimeCount of generated numbers with digits sum of 25 are 10488498
Propably primes 1525141
9.932 s
....
Free Pascal Compiler version 3.0.4 [2018/07/13] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling .code.tio.pp
Linking .bin.tio
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
204 lines compiled, 0.2 sec
Real time: 10.135 s
User time: 10.027 s
Sys. time: 0.052 s
CPU share: 99.45 %
Exit code: 0
</pre>
=={{header|Perl}}==
| |||