PE - Problem 35

Problem 35: 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?

[?1049h[?1h=[1;43r[?12;25h[?12l[?25h[27m[m[H[2J[?25l[2;1H[94m~ [3;1H~ [4;1H~ [5;1H~ [6;1H~ [7;1H~ [8;1H~ [9;1H~ [10;1H~ [11;1H~ [12;1H~ [13;1H~ [14;1H~ [15;1H~ [16;1H~ [17;1H~ [18;1H~ [19;1H~ [20;1H~ [21;1H~ [22;1H~ [23;1H~ [24;1H~ [25;1H~ [26;1H~ [27;1H~ [28;1H~ [29;1H~ [30;1H~ [31;1H~ [32;1H~ [33;1H~ [34;1H~ [35;1H~ [36;1H~ [37;1H~ [38;1H~ [39;1H~ [40;1H~ [41;1H~ [42;1H~ [m[43;175H0,0-1[9CAll[16;88HVIM - Vi IMproved[18;89Hversion 7.4.1099[19;85Hby Bram Moolenaar et al.[20;80HModified by [34m[m[21;75HVim is open source and freely distributable[23;82HBecome a registered Vim user![24;74Htype :help register[34m[m for information [26;74Htype :q[34m[m to exit [27;74Htype :help[34m[m or [34m[m for on-line help[28;74Htype :help version7[34m[m for version info[1;1H[?12l[?25h[?25l[43;1HType :quit to exit Vim[43;175H[K[43;175H0,0-1[9CAll[1;1H[?12l[?25h[?25l[43;175H[K[43;175H0,0-1[9CAll[1;1H[?12l[?25h[?25l[43;175H[K[43;175H0,0-1[9CAll[1;1H[?12l[?25h[?25l[43;175H[K[43;175H0,0-1[9CAll[1;1H[?12l[?25h[43;1H[?1l>[?1049lVim: Error reading input, exiting... Vim: Finished. [43;1H[J

#include <iostream> 
#include <math.h>
#include <string>
using namespace std;

const int UPPER = 1000000;

int power(int b, int x) {
  int result = 1;
  for (int i = 0; i < x; i++) {
    result *= b;
  }
  return result;
}

int rotate(int x) {
  int digits = floor(log10(x)+1);
  int n = power(10, digits-1);
  return (x % n)*10 + floor(x/n);
}

bool isPrime(int x) {
  if (x == 1) return false;
  for (int i = 2; i <= floor(sqrt(x)); i++) {
    if (x % i == 0) return false;
  }
  return true;
}

bool doesContain(int num, int d) {
  int digits = floor(log10(num)+1);
  for (int i = digits; i > 0; i--) {
    if (num % 10 == d)
      return true;
    else
      num /= 10;
  }
  return false;
}


bool isCircular(int x) {
  if (doesContain(x, 0)) return false;
  int rot = floor(log10(x));
  for (int i = 0; i <= rot; i++) {
    if (!isPrime(x)) {
      return false;
    }
  x = rotate(x);
  }
  return true;
}

int main() {
  int count = 0;
  for (int i = 1; i < UPPER; i++) {
   if(isCircular(i)==true) {
      count++;
    }
  }
  cout << count << endl;
}

Answer: 55