Pandigital prime: Difference between revisions
Content added Content deleted
(→{{header|Perl}}: prepend Pascal version nearly {{Trans|Delphi}}) |
|||
Line 227: | Line 227: | ||
0..7: 76,540,231 24.5 μs</pre> |
0..7: 76,540,231 24.5 μs</pre> |
||
=={{header |
=={{header|Delphi}}== |
||
{{works with|Delphi|6.0}} |
|||
{{incorrect|Delphi|76541302 and 7654312 are both even, so definitely not prime.}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="pascal"> |
|||
The original version generated results that weren't prime. This version has been rewritten to fix the prime problem and make it more modular. |
|||
uses System.SysUtils, System.Classes, System.Math; |
|||
label nxt; |
|||
<syntaxhighlight lang="Delphi"> |
|||
{This code is normally put in a separate library, but it is included here for clarity} |
|||
function IsPrime(N: int64): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: int64; |
|||
begin |
begin |
||
if (N = 2) or (N=3) then Result:=true |
|||
for var sp := '0' to '1' do for var x := IfThen(sp = '1', 7654321, 76543210) downto 0 do |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
begin |
|||
else |
|||
var s := x.ToString; |
|||
begin |
|||
for var ch := sp to '7' do if not s.Contains(ch) then goto nxt; |
|||
I:=5; |
|||
if x mod 3 = 0 then goto nxt; |
|||
Stop:=Trunc(sqrt(N+0.0)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
if x mod (i + 4) = 0 then goto nxt; Inc(i, 4); |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
until i * i >= x; |
|||
Inc(I,6); |
|||
Writeln(Format('%s..7: %d', [sp, x])); Break; nxt:; |
|||
end; |
end; |
||
Result:=True; |
|||
end. |
|||
end; |
|||
end; |
|||
function HighestPandigitalPrime(ZeroBased: boolean): integer; |
|||
{Returns the highest pandigital prime} |
|||
{ZeroBased = includes 0..N versus 1..N } |
|||
var I: integer; |
|||
type TDigitFlagArray = array [0..9] of integer; |
|||
procedure GetDigitCounts(N: integer; var FA: TDigitFlagArray); |
|||
{Get a count of all the digits in the number} |
|||
var T,I,DC: integer; |
|||
begin |
|||
DC:=Trunc(Log10(N))+1; |
|||
{Zero counts} |
|||
for I:=0 to High(FA) do FA[I]:=0; |
|||
{Count each time a digits is used} |
|||
for I:=0 to DC-1 do |
|||
begin |
|||
T:=N mod 10; |
|||
N:=N div 10; |
|||
Inc(FA[T]); |
|||
end; |
|||
end; |
|||
function IsPandigital(N: integer): boolean; |
|||
{Checks to see if all digits 0..N or 1..N are included} |
|||
var IA: TDigitFlagArray; |
|||
var I,DC: integer; |
|||
var Start: integer; |
|||
begin |
|||
Result:=False; |
|||
{ZeroBased includes zero} |
|||
if ZeroBased then Start:=0 else Start:=1; |
|||
{Get count of digits} |
|||
DC:=Trunc(Log10(N))+1; |
|||
{Get a count of each digits that are used} |
|||
GetDigitCounts(N,IA); |
|||
{Each digit 0..N or 1..N can only be used once} |
|||
for I:=Start to DC-1 do |
|||
if IA[I]<>1 then exit; |
|||
Result:=True; |
|||
end; |
|||
begin |
|||
if ZeroBased then Result:=76543210+1 else Result:=7654321; |
|||
{Check all numbers in the range} |
|||
while Result>2 do |
|||
begin |
|||
{Check that number is prime and Pandigital} |
|||
if IsPrime(Result) then |
|||
if IsPandigital(Result) then break; |
|||
Dec(Result,2); |
|||
end; |
|||
end; |
|||
procedure PandigitalPrime(Memo: TMemo); |
|||
var P: integer; |
|||
begin |
|||
P:=HighestPandigitalPrime(False); |
|||
Memo.Lines.Add(Format('Non Zero Based: %11.0n',[P+0.0])); |
|||
P:=HighestPandigitalPrime(True); |
|||
Memo.Lines.Add(Format('Zero Based: %11.0n',[P+0.0])); |
|||
end; |
|||
</syntaxhighlight> |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Non Zero Based: 7,652,413 |
|||
0..7: 76541302 |
|||
Zero Based: 76,540,231 |
|||
1..7: 7654312 |
|||
Elapsed Time: 6.044 ms. |
|||
</pre> |
</pre> |
||