Circular primes: Difference between revisions
m
→Embedded: Minor tidy
m (→Embedded: Minor tidy) |
|||
| (13 intermediate revisions by 7 users not shown) | |||
Line 641:
#include <algorithm>
#include <iostream>
#include <gmpxx.h>
Line 648 ⟶ 647:
bool is_prime(const integer& n, int reps = 50) {
return mpz_probab_prime_p(n.get_mpz_t(), reps);
}
Line 659 ⟶ 652:
if (!is_prime(p))
return false;
std::string str = p.get_str(
for (size_t i = 0, n = str.size(); i + 1 < n; ++i) {
std::rotate(str.begin(), str.begin() + 1, str.end());
Line 703 ⟶ 696:
std::cout << "Next 4 circular primes:\n";
p = next_repunit(p);
std::string str = p.get_str(
int digits = str.size();
for (int count = 0; count < 4; ) {
Line 737 ⟶ 730:
R(49081) is probably prime
</pre>
=={{header|D}}==
{{trans|C}}
Line 915 ⟶ 909:
</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#}}==
Line 931 ⟶ 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 1,037 ⟶ 1,081:
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="future basic">
begin globals
Line 1,097 ⟶ 1,141:
end fn
window 1, @"Circular Primes in FutureBasic", (0, 0, 280, 320
t = fn CACurrentMediaTime
fn circularPrimes
Line 1,611 ⟶ 1,655:
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Lazy, Primes
Line 1,647 ⟶ 1,690:
R(49081) is prime.
</pre>
=={{header|Kotlin}}==
{{trans|C}}
Line 2,698 ⟶ 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,742 ⟶ 2,827:
R25031 circular_prime ? false
</pre>
=={{header|Rust}}==
{{trans|C}}
Line 3,041 ⟶ 3,127:
===Wren-cli===
Second part is very slow - over 37 minutes to find all four.
<syntaxhighlight lang="
import "./big" for BigInt
import "./str" for Str
var circs = []
Line 3,118 ⟶ 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="
import "./gmp" for Mpz
Line 3,214 ⟶ 3,301:
R(49081) : true
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N > 2 is a prime number
Line 3,264 ⟶ 3,352:
</pre>
=={{header|Zig}}==
{{works with|Zig|0.11.0}}
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;
pub fn main() !void {
Line 3,275 ⟶ 3,363:
defer arena.deinit();
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 3,301 ⟶ 3,393:
}
fn u32cmp(_: void, a: u32, b: u32) math.Order {
return math.order(a, b);
}
fn circular(n0: u32) bool {
if (!
return false
else {
var n = n0;
var d: u32 = @
return while (d > 0) : (d -= 1) {
n = rotate(n);
if (n < n0 or !
break false;
} else true;
Line 3,323 ⟶ 3,415:
return 0
else {
const d: u32 = @
const m = math.pow(u32, 10, d);
return (n % m) * 10 + n / m;
Line 3,329 ⟶ 3,421:
}
fn
if (n < 2)
return false;
| |||