Problem #35

Here is the code I wrote to solve problem 35. It is just a brute force attempt, it checks every number from [2, 1000000). If it is not a prime in any step, it is eliminated from the test and it goes on to test the next number, if not, it tests the next rotation of the number...quite simple really.

I did have to change the isPrime function to test up to the square root, rather than half of the number. It was really slowing down the process the way it was before, so this is a bit more efficient way of doing that.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool isPrime (int);
bool containsAZero (int);
int rotateOnce (int);

int main()
{
    int total = 0;
    int holder = 0;
    bool prime = true;

    for (unsigned int i = 2; i < 1000000; i++)
        if (!containsAZero (i))
            if (isPrime (i))
            {
                prime = true;
                holder = i;
                for (unsigned int j = 0; j < 6; j++)
                {
                    holder = rotateOnce (holder);
                    if (!isPrime (holder))
                    {
                        prime = false;
                        break;
                    }
                }
                if (prime == true)
                    total++;
            }


    cout << total << endl;

    system ("pause");
    return 0;
}

bool isPrime (int num)
{
    if (num == 1 || num == 2 || num == 3)
        return true;

    for (unsigned int i = 2; i < static_cast<int> (sqrt (static_cast<double> (num))) + 1; i++)
        if (num % i == 0)
            return false;
    return true;
}

bool containsAZero (int num)
{
    char buffer[16];
    string str;

    sprintf (buffer, "%i", num);
    str = buffer;

    for (unsigned int i = 0; i < str.size () - 1; i++)
        if (str[i] == '0')
            return true;
    return false;
}

int rotateOnce (int num)
{
    char buffer[16];
    string str, str2;

    sprintf (buffer, "%i", num);
    str = str2 = buffer;

    for (unsigned int i = 0; i < str.size() - 1; i++)
        str[i] = str2[i+1];
    str[str.size() - 1] = str2[0];

    return atoi (str.c_str ());
}