So I was inspired by a recent Youtube video from the Numberphile Channel. This one to be exact. Cut to around the 5 minute mark for the exact question or example that I am referring to.

TLDR; A number is created with all the digits corresponding to 1 to N. Example: 1 to 10 is the number 12,345,678,910. Find out if this number is prime. According to the video, N has been checked up to 1,000,000.

From the code below, I have taken the liberty of starting this process at 1,000,000 and only going to 10,000,000. I'm hoping to increase this to a larger number later.

So my question or the assistance that I need is optimization for this problem. I'm sure each number will still take very long to check but even a minimal percentage of optimization would go a long way.

Edit 1: Optimize which division numbers are used. Ideally this divisionNumber would only be prime numbers.

Here is the code:

#include <iostream>
#include <chrono>
#include <ctime>

namespace
{
    int myPow(int x, int p)
    {
        if (p == 0) return 1;
        if (p == 1) return x;
        if (p == 2) return x * x;

        int tmp = myPow(x, p / 2);
        if (p % 2 == 0) return tmp * tmp;
        else return x * tmp * tmp;
    }

    int getNumDigits(unsigned int num)
    {
        int count = 0;
        while (num != 0)
        {
            num /= 10;
              count;
        }
        return count;
    }

    unsigned int getDigit(unsigned int num, int position)
    {
        int digit = num % myPow(10, getNumDigits(num) - (position - 1));
        return digit / myPow(10, getNumDigits(num) - position);
    }

    unsigned int getTotalDigits(int num)
    {
        unsigned int total = 0;
        for (int i = 1; i <= num; i  )
            total  = getNumDigits(i);
        return total;
    }

    // Returns the 'index'th digit of number created from 1 to num
    int getIndexDigit(int num, int index)
    {
        if (index <= 9)
            return index;

        for (int i = 10; i <= num; i  )
        {
            if (getTotalDigits(i) >= index)
                return getDigit(i, getNumDigits(i) - (getTotalDigits(i) - index));

        }
    }

    // Can this be optimized?
    int floorSqrt(int x)
    {

        if (x == 0 || x == 1)
            return x;

        int i = 1, result = 1;
        while (result <= x)
        {
            i  ;
            result = i * i;
        }
        return i - 1;
    }

    void PrintTime(double num, int i)
    {
        constexpr double SECONDS_IN_HOUR = 3600;
        constexpr double SECONDS_IN_MINUTE = 60;

        double totalSeconds = num;
        int hours = totalSeconds / SECONDS_IN_HOUR;
        int minutes = (totalSeconds - (hours * SECONDS_IN_HOUR)) / SECONDS_IN_MINUTE;
        int seconds = totalSeconds - (hours * SECONDS_IN_HOUR) - (minutes * SECONDS_IN_MINUTE);

        std::cout << "Elapsed time for " << i << ": " << hours << "h, " << minutes << "m, " << seconds << "s\n";
    }

}

int main()
{
    constexpr unsigned int MAX_NUM_CHECK = 10000000;
    
    for (int i = 1000000; i <= MAX_NUM_CHECK; i  )
    {
        auto start = std::chrono::system_clock::now();
        int digitIndex = 1;

        // Simplifying this to move to the next i in the loop early:
        //      if i % 2 then the last digit is a 0, 2, 4, 6, or 8 and is therefore divisible by 2
        //      if i % 5 then the last digit is 0 or 5 and is therefore divisible by 5
        if (i % 2 == 0 || i % 5 == 0)
        {
            std::cout << i << " not prime" << '\n';
            auto end = std::chrono::system_clock::now();
            std::chrono::duration<double> elapsed_seconds = end - start;
            PrintTime(elapsed_seconds.count(), i);
            continue;
        }

        bool isPrime = true;
        int divisionNumber = 3;
        int floorNum = floorSqrt(i);
        while (divisionNumber <= floorNum && isPrime)
        {
            if (divisionNumber % 5 == 0)
            {
                divisionNumber  = 2;
                continue;
            }

            int number = 0;
            int totalDigits = getTotalDigits(i);
            // This section does the division necessary to iterate through each digit of the 1 to N number
            // Example: Think of dividing 124 into 123456 on paper and how you would iterate through that process

            while (digitIndex <= totalDigits)
            {
                number *= 10;
                number  = getIndexDigit(i, digitIndex);
                number %= divisionNumber;
                digitIndex  ;
            }

            if (number == 0)
            {
                isPrime = false;
                break;
            }
            divisionNumber  = 2;
        }

        if (isPrime)
            std::cout << "N = " << i << " is prime." << '\n';
        else
            std::cout << i << " not prime" << '\n';

        auto end = std::chrono::system_clock::now();
        std::chrono::duration<double> elapsed_seconds = end - start;
        PrintTime(elapsed_seconds.count(), i);

    }
}

CodePudding user response：

Its nice to see you are working on the same question I pondered few months ago. Please refer to question posted in Math Stackexchange for better resources.

TL-DR,
The number you are looking for is called SmarandachePrime.

As per your code, it seems you are dividing with every number that is not a multiple of 2,5. To optimize you can actually check for n = 6k 1 (