Circular primes: Difference between revisions

Line 30:

* [[wp:Repunit|Wikipedia article - Repunit]].

* [[oeis:A016114|OEIS sequence A016114 - Circular primes]].

=={{header|ALGOL 68}}==

<syntaxhighlight lang=algol68>BEGIN # find circular primes - primes where all cyclic permutations #

<syntaxhighlight lang="algol68">BEGIN # find circular primes - primes where all cyclic permutations #

# of the digits are also prime #

# genertes a sieve of circular primes, only the first #

Line 103:

Line 101:

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|ALGOL W}}==

<syntaxhighlight lang=algolw>begin % find circular primes - primes where all cyclic permutations %

<syntaxhighlight lang="algolw">begin % find circular primes - primes where all cyclic permutations %

% of the digits are also prime %

% sets p( 1 :: n ) to a sieve of primes up to n %

Line 179:

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|Arturo}}==

<syntaxhighlight lang=rebol>perms: function [n][

<syntaxhighlight lang="rebol">perms: function [n][

str: repeat to :string n 2

result: new []

Line 238:

Line 234:

193939

199933</pre>

=={{header|AWK}}==

# syntax: GAWK -f CIRCULAR_PRIMES.AWK

BEGIN {

Line 293:

Line 287:

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|C}}==

<syntaxhighlight lang=c>#include <stdbool.h>

<syntaxhighlight lang="c">#include <stdbool.h>

#include <stdint.h>

#include <stdio.h>

Line 409:

Line 402:

R(49081) is probably prime.

</pre>

=={{header|C++}}==

<syntaxhighlight lang=cpp>#include <cstdint>

<syntaxhighlight lang="cpp">#include <cstdint>

#include <algorithm>

#include <iostream>

Line 511:

Line 503:

R(49081) is probably prime

</pre>

=={{header|D}}==

<syntaxhighlight lang=D>import std.bigint;

<syntaxhighlight lang="d">import std.bigint;

import std.stdio;

Line 614:

Line 605:

<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|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#)]

// Circular primes - Nigel Galloway: September 13th., 2021

let fG n g=let rec fG y=if y=g then true else if y>g && isPrime y then fG(10*(y%n)+y/n) else false in fG(10*(g%n)+g/n)

Line 630:

Line 620:

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).

<syntaxhighlight lang=factor>USING: combinators.short-circuit formatting io kernel lists

<syntaxhighlight lang="factor">USING: combinators.short-circuit formatting io kernel lists

lists.lazy math math.combinatorics math.functions math.parser

math.primes sequences sequences.extras ;

Line 671:

Line 660:

R(19) R(23) R(317) R(1031)

</pre>

=={{header|Forth}}==

Forth only supports native sized integers, so we only implement the first part of the task.

create 235-wheel 6 c, 4 c, 2 c, 4 c, 2 c, 4 c, 6 c, 2 c,

does> swap 7 and + c@ ;

Line 737:

Line 725:

2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933

</pre>

=={{header|FreeBASIC}}==

<syntaxhighlight lang=freebasic>#define floor(x) ((x*2.0-0.5)Shr 1)

<syntaxhighlight lang="freebasic">#define floor(x) ((x*2.0-0.5)Shr 1)

Function isPrime(Byval p As Integer) As Boolean

Line 775:

Line 762:

2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933

</pre>

=={{header|Go}}==

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 921:

Line 907:

=={{header|Haskell}}==

Uses arithmoi Library: http://hackage.haskell.org/package/arithmoi-0.10.0.0

<syntaxhighlight lang=haskell>import Math.NumberTheory.Primes (Prime, unPrime, nextPrime)

<syntaxhighlight lang="haskell">import Math.NumberTheory.Primes (Prime, unPrime, nextPrime)

import Math.NumberTheory.Primes.Testing (isPrime, millerRabinV)

import Text.Printf (printf)

Line 992:

Line 978:

</pre>

=={{header|J}}==

R=: [: ". 'x' ,~ #&'1'

Line 1,116:

Line 1,102:

NB. R(2) R(19), R(23) are probably prime.

</pre>

=={{header|Java}}==

<syntaxhighlight lang=java>import java.math.BigInteger;

<syntaxhighlight lang="java">import java.math.BigInteger;

import java.util.Arrays;

Line 1,221:

Line 1,206:

R(25031) is not prime.

</pre>

=={{header|jq}}==

Line 1,231:

Line 1,215:

For an implementation of `is_prime` suitable for the first task, see for example [[Erd%C5%91s-primes#jq]].

def is_circular_prime:

def circle: range(0;length) as $i | .[$i:] + .[:$i];

Line 1,246:

Line 1,230:

</syntaxhighlight>

'''The first task'''

<syntaxhighlight lang=jq>limit(19; circular_primes)</syntaxhighlight>

<syntaxhighlight lang="jq">limit(19; circular_primes)</syntaxhighlight>

'''The second task''' (viewed independently):

last(limit(19; circular_primes)) as $max

| limit(4; repunits | select(. > $max and is_prime))

Line 1,275:

Line 1,259:

199933

</pre>

=={{header|Julia}}==

Note that the evalpoly function used in this program was added in Julia 1.4

<syntaxhighlight lang=julia>using Lazy, Primes

<syntaxhighlight lang="julia">using Lazy, Primes

function iscircularprime(n)

Line 1,314:

Line 1,296:

R(49081) is prime.

</pre>

=={{header|Kotlin}}==

<syntaxhighlight lang=scala>import java.math.BigInteger

<syntaxhighlight lang="scala">import java.math.BigInteger

val SMALL_PRIMES = listOf(

Line 1,445:

Line 1,426:

R(25031) is not prime.

R(35317) is not prime.</pre>

=={{header|Lua}}==

<syntaxhighlight lang=lua>-- Circular primes, in Lua, 6/22/2020 db

<syntaxhighlight lang="lua">-- Circular primes, in Lua, 6/22/2020 db

local function isprime(n)

if n < 2 then return false end

Line 1,477:

Line 1,456:

=={{header|Mathematica}} / {{header|Wolfram Language}}==

<syntaxhighlight lang=~~Mathematica~~>ClearAll[RepUnit, CircularPrimeQ]

<syntaxhighlight lang="mathematica">ClearAll[RepUnit, CircularPrimeQ]

RepUnit[n_] := (10^n - 1)/9

CircularPrimeQ[n_Integer] := Module[{id = IntegerDigits[n], nums, t},

Line 1,515:

Line 1,493:

False

True</pre>

=={{header|Nim}}==

<syntaxhighlight lang=~~Nim~~>import bignum

<syntaxhighlight lang="nim">import bignum

import strformat

Line 1,644:

Line 1,621:

R(35317) is not prime.

R(49081) is probably prime.</pre>

=={{header|Pascal}}==

==={{header|Free Pascal}}===

Line 1,652:

Line 1,628:

199-> 333 and not 311 so a base4 counter 1_(1,3,7,9) changed to base3 3_( 3,7,9 )->base2 7_(7,9) -> base 1 = 99....99.

The main speed up is reached by testing with small primes within CycleNum.

program CircularPrimes;

//nearly the way it is done:

Line 1,845:

Line 1,821:

14 4 247209700 0 8842

that reduces the count of gmp-prime tests to 1/6 </pre>

=={{header|Perl}}==

<syntaxhighlight lang=perl>use strict;

<syntaxhighlight lang="perl">use strict;

use warnings;

use feature 'say';

Line 1,901:

Line 1,876:

R(35317): Prime? False

R(49081): Prime? True</pre>

=={{header|Phix}}==

with javascript_semantics

function circular(integer p)

Line 1,953:

Line 1,927:

===stretch===

(It is probably quite unwise to throw this in the direction of pwa/p2js, I am not even going to bother trying.)

constant t = {5003, 9887, 15073, 25031, 35317, 49081}

printf(1,"The following repunits are probably circular primes:\n")

Line 1,985:

Line 1,959:

diag looping, error code is 1, era is #00644651

</pre>

=={{header|PicoLisp}}==

For small primes, I only check numbers that are made up of the digits 1, 3, 7, and 9, and I also use a small prime checker to avoid the overhead of the Miller-Rabin Primality Test. For the large repunits, one can use the code from the Miller Rabin task.

(load "plcommon/primality.l") # see task: "Miller-Rabin Primality Test"

Line 2,060:

Line 2,033:

(2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933 (R 19) (R 23) (R 317) (R 1031))

</pre>

=={{header|Prolog}}==

Uses a miller-rabin primality tester that I wrote which includes a trial division pass for small prime factors. One could substitute with e.g. the Miller Rabin Primaliy Test task.

Line 2,067:

Line 2,039:

Also the code is smart in that it only checks primes > 9 that are composed of the digits 1, 3, 7, and 9.

?- use_module(library(primality)).

Line 2,114:

Line 2,086:

[2,3,5,7,11,13,17,37,79,113,197,199,337,1193,3779,11939,19937,193939,199933,r(19),r(23),r(317),r(1031)]

</pre>

=={{header|Python}}==

import random

Line 2,230:

Line 2,201:

# because this Miller-Rabin test is already on rosettacode there's no good reason to test the longer repunits.

</syntaxhighlight>

=={{header|Raku}}==

Most of the repunit testing is relatively speedy using the ntheory library. The really slow ones are R(25031), at ~42 seconds and R(49081) at 922(!!) seconds.

<syntaxhighlight lang=raku line>sub isCircular(\n) {

<syntaxhighlight lang="raku" line>sub isCircular(\n) {

return False unless n.is-prime;

my @circular = n.comb;

Line 2,277:

Line 2,247:

R(35317): Prime? False 0.32

R(49081): Prime? True 921.73</pre>

=={{header|REXX}}==

<syntaxhighlight lang=rexx>/*REXX program finds & displays circular primes (with a title & in a horizontal format).*/

<syntaxhighlight lang="rexx">/*REXX program finds & displays circular primes (with a title & in a horizontal format).*/

parse arg N hp . /*obtain optional arguments from the CL*/

if N=='' | N=="," then N= 19 /* " " " " " " */

Line 2,322:

Line 2,291:

2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933

</pre>

=={{header|Ring}}==

see "working..." + nl

see "First 19 circular numbers are:" + nl

Line 2,379:

Line 2,347:

done...

</pre>

=={{header|Ruby}}==

It takes more then 25 minutes to verify that R49081 is probably prime - omitted here.

<syntaxhighlight lang=ruby>require 'gmp'

<syntaxhighlight lang="ruby">require 'gmp'

require 'prime'

candidate_primes = Enumerator.new do |y|

Line 2,426:

Line 2,393:

=={{header|Rust}}==

<syntaxhighlight lang=rust>// [dependencies]

<syntaxhighlight lang="rust">// [dependencies]

// rug = "1.8"

Line 2,547:

Line 2,514:

R(49081) is probably prime.

</pre>

=={{header|Scala}}==

<syntaxhighlight lang=scala>object CircularPrimes {

<syntaxhighlight lang="scala">object CircularPrimes {

def main(args: Array[String]): Unit = {

println("First 19 circular primes:")

Line 2,667:

Line 2,633:

R(15073) is not prime.

R(25031) is not prime.</pre>

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>func is_circular_prime(n) {

<syntaxhighlight lang="ruby">func is_circular_prime(n) {

n.is_prime || return false

Line 2,717:

Line 2,682:

R(35317) -> composite (took: 0.875 sec)

</pre>

=={{header|Wren}}==

Line 2,726:

Line 2,690:

===Wren-cli===

Second part is very slow - over 37 minutes to find all four.

<syntaxhighlight lang=ecmascript>import "/math" for Int

<syntaxhighlight lang="ecmascript">import "/math" for Int

import "/big" for BigInt

import "/str" for Str

Line 2,806:

Line 2,770:

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=ecmascript>/* circular_primes_embedded.wren */

<syntaxhighlight lang="ecmascript">/* circular_primes_embedded.wren */

import "./gmp" for Mpz

Line 2,899:

Line 2,863:

R(49081) : true

</pre>

=={{header|XPL0}}==

<syntaxhighlight lang=~~XPL0~~>func IsPrime(N); \Return 'true' if N > 2 is a prime number

<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N > 2 is a prime number

int N, I;

[if (N&1) = 0 \even number\ then return false;

Line 2,949:

Line 2,912:

2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933

</pre>

=={{header|Zig}}==

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.

const std = @import("std");

const math = std.math;