Circular primes: Difference between revisions

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

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

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

# of the digits are also prime #

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

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

% of the digits are also prime %

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

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

 

str: repeat to :string n 2

result: new []

193939

199933</pre>

=={{header|AWK}}==

# syntax: GAWK -f CIRCULAR_PRIMES.AWK

BEGIN {

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

{{libheader|GMP}}

#include <stdint.h>

#include <stdio.h>

R(49081) is probably prime.

</pre>

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

{{libheader|GMP}}

#include <algorithm>

#include <iostream>

R(49081) is probably prime

</pre>

=={{header|D}}==

{{trans|C}}

import std.stdio;

 

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

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

{{works with|Factor|0.99 2020-03-02}}

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

math.primes sequences sequences.extras ;

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@ ;

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

</pre>

=={{header|FreeBASIC}}==

 

Function isPrime(Byval p As Integer) As Boolean

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

 

import (

=={{header|Haskell}}==

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

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

import Text.Printf (printf)

</pre>

=={{header|J}}==

 

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

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

</pre>

=={{header|Java}}==

import java.util.Arrays;

 

R(25031) is not prime.

</pre>

=={{header|jq}}==

{{works with|jq}}

 

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];

</syntaxhighlight>

'''The first task'''

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

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

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

199933

</pre>

=={{header|Julia}}==

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

 

function iscircularprime(n)

R(49081) is prime.

</pre>

=={{header|Kotlin}}==

{{trans|C}}

 

val SMALL_PRIMES = listOf(

R(25031) is not prime.

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

=={{header|Lua}}==

local function isprime(n)

if n < 2 then return false end

{{out}}

<pre>2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933</pre>

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

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

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

False

True</pre>

=={{header|Nim}}==

{{trans|Kotlin}}

{{libheader|bignum}}

import strformat

 

R(35317) is not prime.

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

=={{header|Pascal}}==

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

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:

14 4 247209700 0 8842

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

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature 'say';

R(35317): Prime? False

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

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">circular</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>

===stretch===

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

<span style="color: #008080;">constant</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5003</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9887</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15073</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25031</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35317</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">49081</span><span style="color: #0000FF;">}</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The following repunits are probably circular primes:\n"</span><span style="color: #0000FF;">)</span>

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"

 

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

 

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

 

[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

 

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

{{libheader|ntheory}}

return False unless n.is-prime;

my @circular = n.comb;

R(35317): Prime? False 0.32

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

=={{header|REXX}}==

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

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

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

done...

</pre>

=={{header|Ruby}}==

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

require 'prime'

candidate_primes = Enumerator.new do |y|

=={{header|Rust}}==

{{trans|C}}

// rug = "1.8"

 

R(49081) is probably prime.

</pre>

=={{header|Scala}}==

{{trans|Java}}

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

println("First 19 circular primes:")

R(15073) is not prime.

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

=={{header|Sidef}}==

{{trans|Raku}}

n.is_prime || return false

 

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

</pre>

=={{header|Wren}}==

{{trans|Go}}

===Wren-cli===

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

import "/big" for BigInt

import "/str" for Str

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

import "./gmp" for Mpz

R(49081) : true

</pre>

=={{header|XPL0}}==

int N, I;

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

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;