Rosetta Code

Pandigital prime: Difference between revisions

Page Discussion

Pandigital prime (view source)

Revision as of 17:09, 13 January 2024

6,955 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added XPL0 example.)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(8 intermediate revisions by 6 users not shown)
Line 182:
<pre>The largest pandigital prime is:
7652413</pre>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="qbasic">#include "isprime.kbs"
 
digits = 7654321
for z = 1 to 0 step -1
print "The largest"; z; "..7 pandigital prime is ";
start = msec
for n = digits to 0 step -18
cadena$ = string(n)
flag = True
for i = z to 7
if instr(cadena$, string(i)) = 0 then
flag = False
exit for
end if
next i
if flag and isPrime(n) then
print rjust(string(n), 8);". "; (msec - start); " ms"
exit for
end if
next n
digits = digits * 10 - 9
next z</syntaxhighlight>
 
==={{header|FreeBASIC}}===
{{trans|Ring}}
<syntaxhighlight lang="freebasic">#include "isprime.bas"
 
Dim As Integer digits = 7654321
For z As Integer = 1 To 0 Step -1
Print "The largest"; z; "..7 pandigital prime is ";
Dim As Double start = Timer
For n As Integer = digits To 0 Step -18
Dim As String cadena = Str(n)
Dim As Boolean flag = True
For i As Integer = z To 7
If Instr(cadena, Str(i)) = 0 Then
flag = False
Exit For
End If
Next i
If flag And isPrime(n) Then
Print Using "########. ##.## ms"; n; (Timer - start) * 10000
Exit For
End If
Next n
digits = digits * 10 - 9
Next z
Sleep</syntaxhighlight>
{{out}}
<pre>The largest 1..7 pandigital prime is 7652413. 6.32 ms
The largest 0..7 pandigital prime is 76540231. 13.95 ms</pre>
 
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Use "isprime.bas"
 
Public Sub Main()
Dim digits As Integer = 7654321
 
For z As Integer = 1 To 0 Step -1
Print "The largest "; z; "..7 pandigital prime is ";
For n As Integer = digits To 0 Step -18
Dim cadena As String = Str(n)
Dim flag As Boolean = True
For i As Integer = z To 7
If InStr(cadena, Str(i)) = 0 Then
flag = False
Break
End If
Next
If flag And isPrime(n) Then
Print Format$(Str$(n), "########"); ". "; Timer; " ms "
Break
End If
Next
digits = digits * 10 - 9
Next
End</syntaxhighlight>
 
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="purebasic">;XIncludeFile "isprime.pb"
 
OpenConsole()
digits.i = 7654321
For z.i = 1 To 0 Step -1
Print("The largest" + Str(z) + "..7 pandigital prime is ")
For n.i = digits To 0 Step -18
cadena.s = Str(n)
flag.b = #True
For i.i = z To 7
If FindString(cadena, Str(i)) = 0:
flag = #False
Break
EndIf
Next i
If flag And isPrime(n):
;Print ""; n; " "; (ElapsedMilliseconds() - start) * 10000; " ms"
PrintN(Str(n) + ". ")
Break
EndIf
Next n
digits = digits * 10 - 9
Next z
 
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()</syntaxhighlight>
 
=={{header|C#|CSharp}}==
Line 227 ⟶ 340:
0..7: 76,540,231 24.5 μs</pre>
 
=={{header|Delphi|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
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;
var i Stop:= 1Trunc(sqrt(N+0.0));
repeat Result:=False;
while I<=Stop do
if x mod (i + 4) = 0 then goto nxt; Inc(i, 4);
if x mod (i + 2) = 0 then goto nxt; Inc(i, 2);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;
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>
{{out}}
<pre>
Non Zero Based: 7,652,413
0..7: 76541302
Zero Based: 76,540,231
1..7: 7654312
Elapsed Time: 6.044 ms.
 
</pre>
 
Line 273 ⟶ 466:
7652413
</pre>
 
 
=={{header|FreeBASIC}}==
{{trans|Ring}}
<syntaxhighlight lang="freebasic">Function isPrime(Byval n As Integer) As Boolean
If n Mod 3 = 0 Then Return False
Dim As Integer i = 5
While i * i < n
If n Mod i = 0 Then Return False : End If : i += 2
If n Mod i = 0 Then Return False : End If : i += 4
Wend
Return True
End Function
 
Dim As Integer digits = 7654321
For z As Integer = 1 To 0 Step -1
Print "The largest"; z; "..7 pandigital prime is ";
Dim As Double start = Timer
For n As Integer = digits To 0 Step -18
Dim As String cadena = Str(n)
Dim As Boolean flag = True
For i As Integer = z To 7
If Instr(cadena, Str(i)) = 0 Then
flag = False
Exit For
End If
Next i
If flag And isPrime(n) Then
Print Using "########. ##.## ms"; n; (Timer - start) * 10000
Exit For
End If
Next n
digits = digits * 10 - 9
Next z
Sleep</syntaxhighlight>
{{out}}
<pre>The largest 1..7 pandigital prime is 7652413. 6.32 ms
The largest 0..7 pandigital prime is 76540231. 13.95 ms</pre>
 
 
=={{header|Go}}==
Line 401 ⟶ 555:
76,540,231
</pre>
 
=={{header|J}}==
<syntaxhighlight lang="j"> gpdp=. >./@({:@(#~ 1&p:)@(10&#.@A.~ i.@!@#)\)
gpdp >: i. 7
7652413
gpdp i. 8
76540231</syntaxhighlight>
 
=={{header|jq}}==
Line 460 ⟶ 622:
</pre>
 
=={{header|MATLAB}}==
'''including zero'''
<syntaxhighlight lang="matlab">
primeNumbers = sum(perms(0:7).*repmat((10*ones(1,8)).^(8-1:-1:0), [factorial(8),1]),'c')
mprintf('The largest pandigital prime is %u.', max(primeNumbers(find(members(primeNumbers, primes(7.7e7))==1))))
</syntaxhighlight>
'''without zero'''
<syntaxhighlight lang="matlab">
primeNumbers = sum(perms(1:7).*repmat((10*ones(1,7)).^(7-1:-1:0), [factorial(7),1]),'c')
mprintf('The largest pandigital prime is %u', max(primeNumbers(find(members(primeNumbers, primes(7.7e6))==1))))
</syntaxhighlight>
 
=={{header|Pascal}}==
=={{header|Free Pascal}}==
nearly {{Trans|Delphi}}
<syntaxhighlight lang="pascal">
program PandigitalPrime;
uses
SysUtils;
type
tDigits = set of 0..7;
const
cPanDigits : array['0'..'1'] of string=('76543210','7654321');
cDigits : array['0'..'1'] of tDigits =([0..7],[1..7]);
var
s : String;
x,i,l : NativeInt;
check,myCheck : tDigits;
sp : char;
begin
for sp := '0' to '1' do
Begin
myCheck := cDigits[sp];
val(cPanDigits[sp],x,i);
l := length(cPanDigits[sp]);
//only odd numbers
IF Not(Odd(x)) then
dec(x);
inc(x,2);
 
repeat
dec(x,2);
//early checking
if x mod 3 = 0 then
continue;
str(x,s);
if length(s)<l then
BREAK;
 
//check pandigital
check := myCheck;
For i := 1 to l do
Exclude(check,Ord(s[i])-Ord('0'));
if check <> [] then
continue;
 
//rest of prime check
i := 5;
repeat
if x mod i = 0 then BREAK;
Inc(i, 2);
if x mod i = 0 then BREAK;
Inc(i, 4);
until i * i >= x;
 
if i*i> x then
Begin
Writeln(Format('%s..7: %d', [sp, x]));
Break;
end;
until x <= 2;
 
end;
end.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>0..7: 76540231
1..7: 7652413
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
Line 699 ⟶ 941:
The largest 0..7 pandigital prime is 76540231 20.30 ms
done...</pre>
 
=={{header|RPL}}==
Based on Factor's insights, we only need to check 4- and 7-digit pandigitals from biggest to smallest.
Rather than generating permutations, we start from the biggest pandigital number for a given number of digits and go backwards by increment of 18, since:
* the difference between 2 pandigital numbers is a multiple of 9
* the biggest pandigital number for a given number of digits is odd and lower candidate numbers must also be odd
{{works with|HP|49}}
« R→I →STR DUP SIZE → d s
« 0
1 s '''FOR''' j
d j DUP SUB STR→ ALOG + '''NEXT''' <span style="color:grey">@ count digit occurrences into a unique number</span>
10 / 9 * 1 + LOG FP NOT <span style="color:grey">@ check that the result is a repunit</span>
» » '<span style="color:blue">ISPAND?</span>' STO
« 0
'''WHILE''' OVER '''REPEAT'''
10 * OVER + SWAP 1 - SWAP '''END'''
NIP 1 CF
DUP XPON ALOG '''FOR''' n
'''IF''' n ISPRIME? '''THEN'''
'''IF''' n <span style="color:blue">ISPAND?</span> '''THEN''' 1 SF n DUP XPON ALOG 'n' STO
'''END END'''
-18 '''STEP'''
'''IF''' 1 FC? '''THEN''' 0 '''END'''
» '<span style="color:blue">PANPRIME</span>' STO
« 7 <span style="color:blue">PANPRIME</span>
'''IF''' DUP NOT '''THEN''' 4 <span style="color:blue">PANPRIME</span> '''END'''
» 'P041' STO
{{out}}
<pre>
1: 7652413
</pre>
 
=={{header|Ruby}}==
Line 749 ⟶ 1,024:
<br>
This makes use of the optimization strategy in the Factor entry to do both the basic and optional tasks.
<syntaxhighlight lang="ecmascriptwren">import "./perm" for Perm
import "./math" for Int
import "./fmt" for Fmt
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339636...355043"