Circular Primes

// Answer: 55

// Authored by: Tim Varley 💘
// Assisted-by: Grok Code Fast via Crush 💘 <crush@charm.land>

#include <iostream>
#include <vector>
#include <string>

int circular_primes() {
    const int MAX = 1000000;
    std::vector<bool> is_prime(MAX+1, true);
    is_prime[0] = is_prime[1] = false;
    for(long long i=2; i*i<=MAX; i++) {
        if(is_prime[i]) {
            for(long long j=i*i; j<=MAX; j+=i) {
                is_prime[j] = false;
            }
        }
    }
    int count = 0;
    for(int n=2; n<MAX; n++) {
        if(!is_prime[n]) continue;
        std::string s = std::to_string(n);
        bool all_prime = true;
        for(size_t rot=1; rot<s.size(); rot++) {
            std::string r = s.substr(rot) + s.substr(0,rot);
            int rn = std::stoi(r);
            if(!is_prime[rn]) { all_prime=false; break; }
        }
        if(all_prime) count++;
    }
    return count;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << circular_primes() << std::endl;
}
#endif // UNITTEST_MODE

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import org.tvarley.euler.util.Prime;

public class Solution035 implements Solution {
  public String solve() {
    int count = 0;
    for (int i = 2; i < 1000000; i++) {
      if (Prime.isPrime(i) && isCircular(i)) count++;
    }
    return Integer.toString(count);
  }

  private boolean isCircular(int n) {
    String s = Integer.toString(n);
    for (int i = 0; i < s.length(); i++) {
      String rot = s.substring(i) + s.substring(0, i);
      if (!Prime.isPrime(Integer.parseInt(rot))) return false;
    }
    return true;
  }
}

module.exports = {
  answer: () => {
    const limit = 1000000;
    const sieve = new Array(limit).fill(true);
    sieve[0] = sieve[1] = false;
    for (let i = 2; i * i < limit; i++) {
      if (sieve[i]) {
        for (let j = i * i; j < limit; j += i) {
          sieve[j] = false;
        }
      }
    }
    const primes = new Set();
    for (let i = 2; i < limit; i++) {
      if (sieve[i]) primes.add(i);
    }

    function isCircular(p) {
      const s = p.toString();
      for (let i = 0; i < s.length; i++) {
        const rotated = s.slice(i) + s.slice(0, i);
        if (!primes.has(parseInt(rotated))) return false;
      }
      return true;
    }

    let count = 0;
    for (const p of primes) {
      if (p < 10 || isCircular(p)) count++;
    }
    return count;
  }
};

def solve():
    """
    Circular Primes
    The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

    There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

    How many circular primes are there below one million?
    https://projecteuler.net/problem=35
    """
    def is_prime(n):
        if n < 2:
            return False
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False
        return True

    def rotations(n):
        s = str(n)
        return [int(s[i:] + s[:i]) for i in range(len(s))]

    count = 0
    for n in range(2, 1000000):
        if all(is_prime(r) for r in rotations(n)):
            count += 1
    return count

package main

import "fmt"

import "strconv"

func isPrime(n int) bool {
  if n < 2 {
    return false
  }
  for i := 2; i*i <= n; i++ {
    if n%i == 0 {
      return false
    }
  }
  return true
}

func rotations(s string) []string {
  res := []string{}
  for i := 0; i < len(s); i++ {
    res = append(res, s[i:]+s[:i])
  }
  return res
}

func main() {
  count := 0
  for n := 2; n < 1000000; n++ {
    if !isPrime(n) {
      continue
    }
    s := strconv.Itoa(n)
    allPrime := true
    for _, rot := range rotations(s) {
      r, _ := strconv.Atoi(rot)
      if !isPrime(r) {
        allPrime = false
        break
      }
    }
    if allPrime {
      count++
    }
  }
  fmt.Println(count)
}

// Answer: 55

fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    if n == 2 || n == 3 {
        return true;
    }
    if n % 2 == 0 || n % 3 == 0 {
        return false;
    }
    let mut i = 5;
    while i * i <= n {
        if n % i == 0 || n % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }
    true
}

pub fn circular_primes() -> u64 {
    let mut count = 0;
    for n in 2..1_000_000 {
        if is_prime(n) {
            let s = format!("{}", n);
            let mut is_circular = true;
            for i in 0..s.len() {
                let rotated: String = s[i..].to_string() + &s[0..i];
                let r: u64 = rotated.parse().unwrap();
                if !is_prime(r) {
                    is_circular = false;
                    break;
                }
            }
            if is_circular {
                count += 1;
            }
        }
    }
    count
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_035() {
        assert_eq!(circular_primes(), 55);
    }
}