Anonymous user
Primes whose sum of digits is 25: Difference between revisions
→{{header|Nanoquery}}: append header pascal
m (→Stretch goal) |
(→{{header|Nanoquery}}: append header pascal) |
||
Line 648:
{{out}}
<pre>997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 </pre>
=={{header|Pascal}}==
added only strechted goal.Generating the numbers by permutation.Same result as [[go]].runtime reduced from 5.8s to 0.4s<BR>
I don't know why the gmp test is so much faster and why there is one more probably prime.
<lang pascal>
program Perm5aus8;
{$IFDEF FPC}
{$mode Delphi}
{$Optimization ON,All}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils,
gmp;
const
cTotalSum = 25;
cMaxCardsOnDeck = cTotalSum;
CMaxCardsUsed = cTotalSum;
type
tDeckIndex = 0..cMaxCardsOnDeck-1;
tSequenceIndex = 0..CMaxCardsUsed-1;
tDiffCardCount = 0..9;
tMengenElem = record
Elemcount : tDeckIndex;
Elem : tDiffCardCount;
end;
tMenge = record
RestMenge : array [low(tDiffCardCount)..High(tDiffCardCount)] of tMengenElem;
MaxUsedIdx,
TotElemCnt : word;
end;
tRestmengen = array [low(tSequenceIndex)..High(tSequenceIndex)+1] of tMenge;
tCardSequence = array [low(tSequenceIndex)..High(tSequenceIndex)] of tDiffCardCount;
tPermRec = packed record
permTiefe : byte;// Stelle der Änderung gegenüber Vorgängerpermutation
permCardSequence :tCardSequence ;
end;
var
// globale Variable, um Stelle der Änderung gegenüber der
// Vorgänger permutation festzuhalten
Restmengen : tRestmengen;
TotalUsedDigits : array[tDeckIndex] of Int32;
ManifoldOfDigit : array[tDiffCardCount] of Int32;
CardSequence : tCardSequence;
CardString : string[cMaxCardsOnDeck+3];
Count: NativeInt;
PermCount : integer;
mindepth : integer;
//*****************************************************************************
procedure MengeInit(var ioMenge:tMenge);
var
i : integer;
begin
with ioMenge do
begin
MaxUsedIdx := 0;
For i := Low(tDiffCardCount) to High(tDiffCardCount) do
with RestMenge[i] do
begin
ElemCount := 0;
Elem := 0;
end;
end;
end;
procedure CheckPrime(LastDigit:NativeInt);
var
z : mpz_t;
begin
if Lastdigit in [1,3,7,9] then
Begin
mpz_init_set_str(z,pChar(@CardString[1]),10);
if mpz_probab_prime_p(z,1)>0 then
inc(count);
mpz_clear(z);
end;
end;
procedure Permute(depth,MaxCardsUsed:integer);
var
i : NativeInt;
pMengeElem : ^tMengenElem;
begin
i := 0;
pMengeElem := @RestMengen[depth].RestMenge[i];
repeat
if pMengeElem^.Elemcount <> 0 then begin
//take element
dec(pMengeElem^.ElemCount);
//insert in result here string too
CardSequence[depth] := pMengeElem^.Elem;
CardString[depth+1] := chr(pMengeElem^.Elem+Ord('0'));
//done one permutation
IF depth = MaxCardsUsed then begin
inc(permCount);
// ###########
setlength(CardString,depth+1);
CardString[ depth+2] := #0;
CheckPrime(CardSequence[depth]);
// ###########
mindepth := depth;
end
else begin
RestMengen[depth+1]:= RestMengen[depth];
Permute(depth+1,MaxCardsUsed);
//insert element
inc(pMengeElem^.ElemCount);
dec(minDepth);
end;
end;
inc(pMengeElem);
inc(i);
until i >=RestMengen[depth].MaxUsedIdx;
end;
procedure Check(n:nativeInt);
var
i,dgtCnt,cnt,dgtIdx : NativeInt;
Begin
MengeInit(Restmengen[0]);
dgtCnt := 0;
dgtIdx := 0;
with Restmengen[0] do
Begin
For i in tDiffCardCount do
Begin
cnt := ManifoldOfDigit[i];
if cnt > 0 then
Begin
with RestMenge[dgtIdx] do
Begin
Elemcount := cnt;
Elem := i;
end;
inc(dgtCnt,cnt);
inc(dgtIdx);
end;
end;
MaxUsedIdx := dgtIdx;
end;
permute(0,dgtCnt-1);
end;
procedure AppendToSum(n,dgt,remsum:NativeInt);
var
i: NativeInt;
begin
inc(ManifoldOfDigit[dgt]);
IF remsum > 0 then
For i := dgt to 9 do
AppendToSum(n+1,i,remsum-i)
else
Begin
if remsum = 0 then
Begin
Check(n);
inc(TotalUsedDigits[n]);
end;
end;
dec(ManifoldOfDigit[dgt]);
end;
var
i :NativeInt;
BEGIN
permcount:=0;
fillchar(ManifoldOfDigit[0],SizeOf(ManifoldOfDigit),#0);
count := 0;
For i := 1 to 9 do
AppendToSum(0,i,cTotalSum-i);
writeln('Count of generated numbers with digits sum of ',cTotalSum,' are ',permcount);
Writeln('Propably primes ',count);
//For i := 0 to cTotalSum-1 do writeln(i+1:3,TotalUsedDigits[i]:10); writeln;
END.</lang>
{{out}}
<pre>
Count of generated numbers with digits sum of 25 are 16499120
Propably primes 1525142<pre>
real 0m6,875s
=={{header|Perl}}==
| |||