Rosetta Code

Circular primes: Difference between revisions

Page Discussion

Circular primes (view source)

Revision as of 09:48, 20 November 2023

9,599 bytes added ,  5 months ago
m
→‎Embedded: Minor tidy
m (Automated syntax highlighting fixup (second round - minor fixes))
m (→‎Embedded: Minor tidy)
 
(20 intermediate revisions by 11 users not shown)
Line 176:
First 19 circular primes: 2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933
</pre>
 
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat
return true
end isPrime
 
on isCircularPrime(n)
if (not isPrime(n)) then return false
set temp to n
set c to 0
repeat while (temp > 9)
set temp to temp div 10
set c to c + 1
end repeat
set p to (10 ^ c) as integer
set temp to n
repeat c times
set temp to temp mod p * 10 + temp div p
if ((temp < n) or (not isPrime(temp))) then return false
end repeat
return true
end isCircularPrime
 
-- Return the first c circular primes.
-- Takes 2 as read and checks only odd numbers thereafter.
on circularPrimes(c)
if (c < 1) then return {}
set output to {2}
set n to 3
set counter to 1
repeat until (counter = c)
if (isCircularPrime(n)) then
set end of output to n
set counter to counter + 1
end if
set n to n + 2
end repeat
return output
end circularPrimes
 
return circularPrimes(19)</syntaxhighlight>
 
{{output}}
<syntaxhighlight lang="applescript">{2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933}</syntaxhighlight>
 
=={{header|Arturo}}==
 
Line 287 ⟶ 338:
first 19 circular primes: 2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933
</pre>
 
 
=={{header|BASIC}}==
Rosetta Code problem: https://rosettacode.org/wiki/Circular_primes
by Jjuanhdez, 02/2023
 
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="freebasic">p = 2
dp = 1
cont = 0
print("Primeros 19 primos circulares:")
while cont < 19
if isCircularPrime(p) then print p;" "; : cont += 1
p += dp
dp = 2
end while
end
 
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
 
function isCircularPrime(p)
n = floor(log(p)/log(10))
m = 10^n
q = p
for i = 0 to n
if (q < p or not isPrime(q)) then return false
q = (q mod m) * 10 + floor(q / m)
next i
return true
end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
 
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">#define floor(x) ((x*2.0-0.5) Shr 1)
 
Function isPrime(Byval p As Integer) As Boolean
If p < 2 Then Return False
If p Mod 2 = 0 Then Return p = 2
If p Mod 3 = 0 Then Return p = 3
Dim As Integer d = 5
While d * d <= p
If p Mod d = 0 Then Return False Else d += 2
If p Mod d = 0 Then Return False Else d += 4
Wend
Return True
End Function
 
Function isCircularPrime(Byval p As Integer) As Boolean
Dim As Integer n = floor(Log(p)/Log(10))
Dim As Integer m = 10^n, q = p
For i As Integer = 0 To n
If (q < p Or Not isPrime(q)) Then Return false
q = (q Mod m) * 10 + floor(q / m)
Next i
Return true
End Function
 
Dim As Integer p = 2, dp = 1, cont = 0
Print("Primeros 19 primos circulares:")
While cont < 19
If isCircularPrime(p) Then Print p;" "; : cont += 1
p += dp: dp = 2
Wend
Sleep</syntaxhighlight>
{{out}}
<pre>
Primeros 19 primos circulares:
2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933
</pre>
 
 
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="PureBasic">Macro floor(x)
Round(x, #PB_Round_Down)
EndMacro
 
Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
 
Procedure isCircularPrime(p.i)
n.i = floor(Log(p)/Log(10))
m.i = Pow(10, n)
q.i = p
For i.i = 0 To n
If q < p Or Not isPrime(q)
ProcedureReturn #False
EndIf
q = (q % m) * 10 + floor(q / m)
Next i
ProcedureReturn #True
EndProcedure
 
OpenConsole()
 
p.i = 2
dp.i = 1
cont.i = 0
PrintN("Primeros 19 primos circulares:")
While cont < 19
If isCircularPrime(p)
Print(Str(p) + " ")
cont + 1
EndIf
p + dp
dp = 2
Wend
 
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
 
==={{header|Yabasic}}===
<syntaxhighlight lang="freebasic">p = 2
dp = 1
cont = 0
print("Primeros 19 primos circulares:")
while cont < 19
if isCircularPrime(p) then
print p," ";
cont = cont + 1
fi
p = p + dp
dp = 2
wend
end
 
sub isPrime(v)
if v < 2 return False
if mod(v, 2) = 0 return v = 2
if mod(v, 3) = 0 return v = 3
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
 
sub isCircularPrime(p)
n = floor(log(p)/log(10))
m = 10^n
q = p
for i = 0 to n
if (q < p or not isPrime(q)) return false
q = (mod(q, m)) * 10 + floor(q / m)
next i
return true
end sub</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
 
=={{header|C}}==
{{libheader|GMP}}
Line 407 ⟶ 641:
#include <algorithm>
#include <iostream>
#include <sstream>
#include <gmpxx.h>
 
Line 414 ⟶ 647:
bool is_prime(const integer& n, int reps = 50) {
return mpz_probab_prime_p(n.get_mpz_t(), reps);
}
 
std::string to_string(const integer& n) {
std::ostringstream out;
out << n;
return out.str();
}
 
Line 425 ⟶ 652:
if (!is_prime(p))
return false;
std::string str = p.get_str(to_string(p));
for (size_t i = 0, n = str.size(); i + 1 < n; ++i) {
std::rotate(str.begin(), str.begin() + 1, str.end());
Line 469 ⟶ 696:
std::cout << "Next 4 circular primes:\n";
p = next_repunit(p);
std::string str = p.get_str(to_string(p));
int digits = str.size();
for (int count = 0; count < 4; ) {
Line 503 ⟶ 730:
R(49081) is probably prime
</pre>
 
=={{header|D}}==
{{trans|C}}
Line 605 ⟶ 833:
<pre>First 19 circular primes:
2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933</pre>
 
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Again note how the code is broken up into easy to distinguish subroutines that can be reused, as opposed to mashing everything together into a mass of code that is difficult to understand, debug or enhance.
 
<syntaxhighlight lang="Delphi">
procedure ShowCircularPrimes(Memo: TMemo);
{Show list of the first 19, cicular primes}
var I,Cnt: integer;
var S: string;
 
 
 
procedure RotateStr(var S: string);
{Rotate characters in string}
var I: integer;
var C: char;
begin
C:=S[Length(S)];
for I:=Length(S)-1 downto 1 do S[I+1]:=S[I];
S[1]:=C;
end;
 
 
function IsCircularPrime(N: integer): boolean;
{Test if all rotations of number are prime and}
{A rotation of the number hasn't been used before}
var I,P: integer;
var NS: string;
begin
Result:=False;
NS:=IntToStr(N);
for I:=1 to Length(NS)-1 do
begin
{Rotate string and convert to integer}
RotateStr(NS);
P:=StrToInt(NS);
{Exit if number is not prime or}
{Is prime, is less than N i.e. we've seen it before}
if not IsPrime(P) or (P<N) then exit;
end;
Result:=True;
end;
 
begin
S:='';
Cnt:=0;
{Look for circular primes and display 1st 19}
for I:=0 to High(I) do
if IsPrime(I) then
if IsCircularPrime(I) then
begin
Inc(Cnt);
S:=S+Format('%7D',[I]);
if Cnt>=19 then break;
If (Cnt mod 5)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count = '+IntToStr(Cnt));
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11
13 17 37 79 113
197 199 337 1193 3779
11939 19937 193939 199933
Count = 19
Elapsed Time: 21.234 ms.
 
</pre>
 
 
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang="easylang">
fastfunc prime n .
if n mod 2 = 0 and n > 2
return 0
.
i = 3
sq = sqrt n
while i <= sq
if n mod i = 0
return 0
.
i += 2
.
return 1
.
func cycle n .
m = n
p = 1
while m >= 10
p *= 10
m = m div 10
.
return m + n mod p * 10
.
func circprime p .
if prime p = 0
return 0
.
p2 = cycle p
while p2 <> p
if p2 < p or prime p2 = 0
return 0
.
p2 = cycle p2
.
return 1
.
p = 2
while count < 19
if circprime p = 1
print p
count += 1
.
p += 1
.
</syntaxhighlight>
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Repunit_primes#F.23 rUnitP] and [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
Line 620 ⟶ 974:
The first 5 repunit primes are R(2) R(19) R(23) R(317) R(1031)
</pre>
 
=={{header|Factor}}==
Unfortunately Factor's miller-rabin test or bignums aren't quite up to the task of finding the next four circular prime repunits in a reasonable time. It takes ~90 seconds to check R(7)-R(1031).
Line 725 ⟶ 1,080:
2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933
</pre>
=={{header|FreeBASICFutureBasic}}==
<syntaxhighlight lang="freebasicfuture basic">#define floor(x) ((x*2.0-0.5)Shr 1)
 
begin globals
Function isPrime(Byval p As Integer) As Boolean
_last1 = 7
If p < 2 Then Return False
CFTimeInterval t
If p Mod 2 = 0 Then Return p = 2
byte n(_last1 +1) //array of digits
If p Mod 3 = 0 Then Return p = 3
uint64 list(20), p10 = 1
Dim As Integer d = 5
short count, digits, first1 = _last1
While d * d <= p
n(_last1) = 2 //First number to check
If p Mod d = 0 Then Return False Else d += 2
end globals
If p Mod d = 0 Then Return False Else d += 4
Wend
Return True
End Function
 
local fn convertToNumber as uint64
Function isCircularPrime(Byval p As Integer) As Boolean
short i = first1
Dim As Integer n = floor(Log(p)/Log(10))
uint64 nr = n(i)
Dim As Integer m = 10^n, q = p
while i < _last1
For i As Integer = 0 To n
i++ : nr = Ifnr (q* <10 p+ Or Not isPrimen(qi)) Then Return false
wend
q = (q Mod m) * 10 + floor(q / m)
end fn = nr
Next i
Return true
End Function
 
void local fn increment( dgt as short )
Dim As Integer p = 2, dp = 1, cont = 0
select n(dgt)
Print("Primeros 19 primos circulares:")
case 1, 7, 5 : n(dgt) += 2
While cont < 19
case 3 : if digits then n(dgt) = 7 else n(dgt) = 5
If isCircularPrime(p) Then Print p;" "; : cont += 1
pcase 9 += dp: dp n(dgt) = 21
if dgt == first1 then first1-- : digits++ : p10 *= 10
Wend
fn increment( dgt -1 )
Sleep</syntaxhighlight>
case else : n(dgt)++
end select
end fn
 
local fn isPrime( v as uint64 ) as bool
if v < 4 then exit fn = yes
if v mod 3 == 0 then exit fn = no
uint64 f = 5
while f*f <= v
if v mod f == 0 then exit fn = no
f += 2
if v mod f == 0 then exit fn = no
f += 4
wend
end fn = yes
 
void local fn circularPrimes
uint64 num, nr
short r
while ( count < 19 )
num = fn convertToNumber
if fn isPrime( num )
nr = num
for r = 1 to digits
nr = 10 * ( nr mod p10 ) + ( nr / p10 ) //Rotate
if nr < num then break //Rotation of lower number
if fn isPrime( nr ) == no then break //Not prime
next
if r > digits then list( count ) = num : count++
end if
fn increment( _last1 )
wend
end fn
 
window 1, @"Circular Primes in FutureBasic", (0, 0, 280, 320)
t = fn CACurrentMediaTime
fn circularPrimes
t = fn CACurrentMediaTime - t
for count = 0 to 18
printf @"%22u",list(count)
next
printf @"\n Compute time: %.3f ms", t * 1000
handleevents
 
</syntaxhighlight>
{{out}}
[[File:Screenshot of Circular Primes in FutureBasic.png]]
<pre>
 
Primeros 19 primos circulares:
2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933
</pre>
=={{header|Go}}==
{{libheader|GMP(Go wrapper)}}
Line 905 ⟶ 1,298:
R(49081) : true
</pre>
 
=={{header|Haskell}}==
Uses arithmoi Library: http://hackage.haskell.org/package/arithmoi-0.10.0.0
Line 980 ⟶ 1,374:
<syntaxhighlight lang="j">
 
R=: [:10x "#. 'x' ,~ #&'1'
assert 11111111111111111111111111111111x -: R 32
 
Line 1,051 ⟶ 1,445:
<pre>
Note 'The current Miller-Rabin test implemented in c is insufficient for this task'
R=: ([:10x "#. 'x' ,~ #&'1')&>
(;q:@R)&> 500
|limit error
Line 1,060 ⟶ 1,454:
Filter=: (#~`)(`:6)
 
R=: ([:10x "#. 'x' ,~ #&'1')&>
(; q:@R)&> (0 ~: 3&|)Filter >: i. 26 NB. factor some repunits
┌──┬─────────────────────────────────┐
Line 1,102 ⟶ 1,496:
NB. R(2) R(19), R(23) are probably prime.
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">import java.math.BigInteger;
Line 1,260 ⟶ 1,655:
</pre>
=={{header|Julia}}==
Note that the evalpoly function used in this program was added in Julia 1.4
<syntaxhighlight lang="julia">using Lazy, Primes
 
Line 1,296 ⟶ 1,690:
R(49081) is prime.
</pre>
 
=={{header|Kotlin}}==
{{trans|C}}
Line 2,347 ⟶ 2,742:
done...
</pre>
=={{header|RPL}}==
To speed up execution, we use a generator of candidate numbers made only of 1, 3, 7 and 9.
{{works with|HP|49}}
≪ 1 SF DUP
'''DO'''
→STR TAIL LASTARG HEAD + STR→
'''CASE'''
DUP2 > OVER 3 MOD NOT OR '''THEN''' 1 CF '''END'''
DUP ISPRIME? NOT '''THEN''' 1 CF '''END'''
'''END'''
'''UNTIL''' DUP2 == 1 FC? OR '''END'''
DROP2 1 FS?
≫ '<span style="color:blue">CIRC?</span>' STO
≪ →STR "9731" → prev digits
≪ 1 SF "" <span style="color:grey">@ flag 1 set = carry</span>
prev SIZE 1 '''FOR''' j
digits DUP
prev j DUP SUB POS 1 FS? -
'''IF''' DUP NOT '''THEN''' DROP digits SIZE '''ELSE''' 1 CF '''END'''
DUP SUB SWAP +
-1 '''STEP'''
'''IF''' 1 FS? '''THEN''' digits DUP SIZE DUP SUB SWAP + '''END'''
STR→
≫ ≫ '<span style="color:blue">NEXT1379</span>' STO
≪ 2 CF { 2 3 5 7 } 7
DO
<span style="color:blue">NEXT1379</span>
'''IF''' DUP <span style="color:blue">CIRC?</span> '''THEN'''
SWAP OVER + SWAP
'''IF''' OVER SIZE 19 ≥ '''THEN''' 2 SF '''END'''
'''END'''
'''UNTIL''' 2 FS? '''END''' DROP
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933 }
</pre>
Runs in 13 minutes 10 seconds on a HP-50g.
 
=={{header|Ruby}}==
It takes more then 25 minutes to verify that R49081 is probably prime - omitted here.
Line 2,391 ⟶ 2,827:
R25031 circular_prime ? false
</pre>
 
=={{header|Rust}}==
{{trans|C}}
Line 2,690 ⟶ 3,127:
===Wren-cli===
Second part is very slow - over 37 minutes to find all four.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./big" for BigInt
import "./str" for Str
var circs = []
Line 2,767 ⟶ 3,204:
</pre>
<br>
 
===Embedded===
{{libheader|Wren-gmp}}
A massive speed-up, of course, when GMP is plugged in for the 'probably prime' calculations. 11 minutes 19 seconds including the stretch goal.
<syntaxhighlight lang="ecmascriptwren">/* circular_primes_embeddedCircular_primes_embedded.wren */
import "./gmp" for Mpz
Line 2,863 ⟶ 3,301:
R(49081) : true
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N > 2 is a prime number
Line 2,913 ⟶ 3,352:
</pre>
=={{header|Zig}}==
{{works with|Zig|0.11.0}}
As of now (Zig release 0.8.1), Zig has large integer support, but there is not yet a prime test in the standard library. Therefore, we only find the circular primes < 1e6. As with the Prolog version, we only check numbers composed of 1, 3, 7, or 9.
Zig has large integer support, but there is not yet a prime test in the standard library. Therefore, we only find the circular primes < 1e6. As with the Prolog version, we only check numbers composed of 1, 3, 7, or 9.
<syntaxhighlight lang="zig">
const std = @import("std");
const math = std.math;
const heap = std.heap;
const stdout = std.io.getStdOut().writer();
 
pub fn main() !void {
Line 2,924 ⟶ 3,363:
defer arena.deinit();
 
varconst candidatesallocator = std.PriorityQueue(u32).init(&arena.allocator, u32cmp();
 
var candidates = std.PriorityQueue(u32, void, u32cmp).init(allocator, {});
defer candidates.deinit();
 
const stdout = std.io.getStdOut().writer();
 
try stdout.print("The circular primes are:\n", .{});
Line 2,950 ⟶ 3,393:
}
 
fn u32cmp(_: void, a: u32, b: u32) math.Order {
return math.order(a, b);
}
 
fn circular(n0: u32) bool {
if (!isprimeisPrime(n0))
return false
else {
var n = n0;
var d: u32 = @floatToIntintFromFloat(u32, @log10(@intToFloatas(f32, @floatFromInt(n))));
return while (d > 0) : (d -= 1) {
n = rotate(n);
if (n < n0 or !isprimeisPrime(n))
break false;
} else true;
Line 2,972 ⟶ 3,415:
return 0
else {
const d: u32 = @floatToIntintFromFloat(u32, @log10(@intToFloatas(f32, @floatFromInt(n)))); // digit count - 1
const m = math.pow(u32, 10, d);
return (n % m) * 10 + n / m;
Line 2,978 ⟶ 3,421:
}
 
fn isprimeisPrime(n: u32) bool {
if (n < 2)
return false;
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/329267...354162"