Primes whose sum of digits is 25: Difference between revisions
Content added Content deleted
m (→Stretch goal) |
(→{{header|Nanoquery}}: append header pascal) |
||
Line 648: | Line 648: | ||
{{out}} |
{{out}} |
||
<pre>997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 </pre> |
<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}}== |
=={{header|Perl}}== |