Circular primes: Difference between revisions

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

# of the digits are also prime #

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

OD;

print( ( newline ) )

{{out}}

<pre>

=={{header|ALGOL W}}==

% of the digits are also prime %

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

end for_i ;

end_circular:

{{out}}

<pre>

=={{header|Arturo}}==

str: repeat to :string n 2

result: new []

]

i: i + 1

{{out}}

=={{header|AWK}}==

# syntax: GAWK -f CIRCULAR_PRIMES.AWK

BEGIN {

return(1)

}

{{out}}

<pre>

=={{header|C}}==

{{libheader|GMP}}

#include <stdint.h>

#include <stdio.h>

test_repunit(49081);

return 0;

{{out}}

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

{{libheader|GMP}}

#include <algorithm>

#include <iostream>

test_repunit(49081);

return 0;

{{out}}

=={{header|D}}==

{{trans|C}}

import std.stdio;

}

writeln;

{{out}}

<pre>First 19 circular primes:

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

circP()|> Seq.take 19 |>Seq.iter(printf "%d "); printfn ""

printf "The first 5 repunit primes are "; rUnitP(10)|>Seq.take 5|>Seq.iter(fun n->printf $"R(%d{n}) "); printfn ""

{{out}}

<pre>

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 ;

"The next 4 circular primes, in repunit format, are:" print

{{out}}

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

." The first 19 circular primes are:" cr .primes cr

bye

{{Out}}

<pre>

=={{header|FreeBASIC}}==

Function isPrime(Byval p As Integer) As Boolean

p += dp: dp = 2

Wend

{{out}}

<pre>

=={{header|Go}}==

{{libheader|GMP(Go wrapper)}}

import (

fmt.Printf("R(%-5d) : %t\n", i, repunit(i).ProbablyPrime(10))

}

{{out}}

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

circular = show . take 19 . filter (isCircular False)

reps = map (sum . digits). tail . take 5 . filter (isCircular True)

{{out}}

<pre>

</pre>

=={{header|J}}==

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

group </. P

)

J lends itself to investigation. Demonstrate and play with the definitions.

<pre>

=={{header|Java}}==

import java.util.Arrays;

return new BigInteger(new String(ch));

}

{{out}}

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

def repunits:

1 | recurse(10*. + 1);

'''The first task'''

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

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

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

{{out}}

For the first task:

=={{header|Julia}}==

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

function iscircularprime(n)

println("R($i) is ", isprimerepunit(i) ? "prime." : "not prime.")

end

<pre>

The first 19 circular primes are:

=={{header|Kotlin}}==

{{trans|C}}

val SMALL_PRIMES = listOf(

testRepUnit(35317)

testRepUnit(49081)

{{out}}

<pre>First 19 circular primes:

=={{header|Lua}}==

local function isprime(n)

if n < 2 then return false end

p, dp = p + dp, 2

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

]

{{out}}

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

{{trans|Kotlin}}

{{libheader|bignum}}

import strformat

testRepUnit(25031)

testRepUnit(35317)

{{out}}

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:

{$ENDIF}

end.

{{Out|@ Tio.Run}}

<pre>

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature 'say';

for (5003, 9887, 15073, 25031, 35317, 49081) {

say "R($_): Prime? " . (is_prime 1 x $_ ? 'True' : 'False');

{{out}}

<pre>The first 19 circular primes are:

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

<span style="color: #008080;">end</span> <span style="color: #008080;">while</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 next 4 circular primes, in repunit format, are:\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)})</span>

{{out}}

<pre>

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

<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;">"R(%d) : %t (%s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bPrime</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

64-bit can only cope with the first five (it terminates abruptly on the sixth)<br>

=={{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"

(println Circular)

(bye)

{{Out}}

<pre>

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

?- main.

{{Out}}

<pre>

=={{header|Python}}==

import random

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

=={{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;

my $now = now;

say "R($_): Prime? ", ?is_prime("{1 x $_}"), " {(now - $now).fmt: '%.2f'}"

{{out}}

<pre>The first 19 circular primes are:

=={{header|REXX}}==

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

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

end /*k*/ /* [↓] a prime (J) has been found. */

#= #+1; !.j= 1; sq.#= j*j; @.#= j /*bump P cnt; assign P to @. and !. */

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ring}}==

see "working..." + nl

see "First 19 circular numbers are:" + nl

next

return 1

{{out}}

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

puts reps.map{|r| "R" + r.to_s}.join(", "), ""

[5003, 9887, 15073, 25031].each {|rep| puts "R#{rep} circular_prime ? #{circular?("1"*rep)}" }

{{out}}

<pre>First 19 circular primes:

=={{header|Rust}}==

{{trans|C}}

// rug = "1.8"

test_repunit(35317);

test_repunit(49081);

{{out}}

=={{header|Scala}}==

{{trans|Java}}

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

println("First 19 circular primes:")

BigInt.apply(new String(ch))

}

{{out}}

<pre>First 19 circular primes:

=={{header|Sidef}}==

{{trans|Raku}}

n.is_prime || return false

say ("R(#{n}) -> ", is_prob_prime((10**n - 1)/9) ? 'probably prime' : 'composite',

" (took: #{'%.3f' % Time.micro-now} sec)")

{{out}}

<pre>

===Wren-cli===

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

import "/big" for BigInt

import "/str" for Str

}

}

{{out}}

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

repunit.setStr(Str.repeat("1", i), 10)

Fmt.print("R($-5d) : $s", i, repunit.probPrime(15) > 0)

<br>

=={{header|XPL0}}==

int N, I;

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

N:= N+2;

];

{{out}}

=={{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;

} else true;

}

{{Out}}

<pre>