Question

How to check if a number is circular prime (cyclically rotate left will also be prime) in C++

Answer 1

#include <iostream>
 
bool is_prime(uint32_t n) {
    if (n == 2)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
    for (uint32_t i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
 
    return true;
}
 
uint32_t cyclically_rotate_left(uint32_t n) {
    uint32_t m = n, p = 1;
    while (m >= 10) {
        p *= 10;
        m /= 10;
    }
 
    return m + 10 * (n % p);
}
 
bool is_circular_prime(uint32_t n) {
    if (!is_prime(n))
        return false;
 
    uint32_t rotated_n = cyclically_rotate_left(n);
    while (rotated_n != n) {
        if (rotated_n < n || !is_prime(rotated_n))
            return false;
        rotated_n = cyclically_rotate_left(rotated_n);
    }
    return true;
}
 
int main() {
    // 3779 = prime
    // 7793 = prime
    // 7937 = prime
    // 9377 = prime

    std::cout << (is_circular_prime(3779) ? "yes" : "no");
}
 
 
 
 
/*
run:
 
yes
 
*/

 

70+ SQL courses for beginners and professionals