Task — Circular prime

Write a script to find out first 10 circular primes having at least 3 digits (base 10). A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will also be prime.

Please check Wikipedia for more information.

Examples

Example 1:
113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 
199933 are circular primes. For exaample, 197 is a 
circular prime because 197, 971 and 719 are all prime.

Analysis

Although not stated, but implied by the supplied answer, the answers are all the lowest value permutation of the given string of digits - so for example 197 is an answer, but not 719 or 971.

My simple solution uses good old Eratosthenes's sieve to generate the primes. Then for each prime we can permute the digits, immediately moving on the next candidate if:

• the permuted value is not prime, or
• the permuted value matches an already-identified circular prime (for the reason stated above)

Since Mohammad was kind enough to share the answer, we know that the 10th circular prime is a 6-digit number - 199 933 - and we might be tempted to limit the size of our sieve to that number. However, some of its permutations considerably exceed the number itself, for example 999 331, so I ran the sieve up to 1 000 000.

I debated how to permute the digits of a multidigit number and settled on:

$c =~ m|(.*)(.)|;
$c = $2 . $1;

It's been stated in previous reviews that substr() is faster:

$c = substr($c, 1, 99) . substr($c, 0, 1);

but the difference in this case is negligible.

#!/usr/bin/perl

# Peter Campbell Smith - 2022-05-30
# PWC 167 task 1

use v5.26;
use strict;
use warnings;
use utf8;

my (@sieve, $count, $j, $c, $results, @seen);

# make sieve
@sieve = make_sieve(1000000);

# seek circular primes > 100
$count = 0;
OUTER: for $j (100 .. 1000000) {
    # skip $j if not prime
    next unless $sieve[$j];
    
    # permute the digits of $j
    $c = $j;
    while (1) {
        
        # take the last digit and make it the first
        $c =~ m|(.*)(.)|;
        $c = $2 . $1;
        
        # finish if we're back where we started
        last if $c == $j;
        
        # no good if the permuted number is not prime or it's a permutation
        # of a circular prime we've already found
        next OUTER if (not $sieve[$c] or $seen[$c]);
    }
    
    # result!!
    $seen[$j] = 1;
    
    $results .= qq[$j, ];
    last if $count++ == 10;
}
say qq[\nThe following are circular primes:\n] . substr($results, 0, -2);

sub make_sieve {
    
    # make sieve of Eratosthenes - $j is prime if $sieve[$j];
    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = $_[0];
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }
    
    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime     
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
    return @sieve;
}

Output

The following are circular primes:
113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933