Question

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

Answer 1

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

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() {
    printf("%s", is_circular_prime(3779) ? "yes" : "no");

    // 3779 = prime
    // 7793 = prime
    // 7937 = prime
    // 9377 = prime

    return 0;
}




/*
run:

yes

*/

 

70+ SQL courses for beginners and professionals