c++ - 查找一对 N 是素数优化

Question

所以我受到了 Numberphile channel 最近的 Youtube 视频的启发。准确地说，This one。针对我所指的确切问题或示例，将时间缩短到 5 分钟左右。

TLDR；创建一个数字，其中所有数字对应于 1 到 N。示例:1 到 10 是数字 12,345,678,910。判断这个数是否是质数。根据视频，N 已被检查多达 1,000,000 个。

从下面的代码中，我冒昧地从 1,000,000 开始此过程，并且仅达到 10,000,000。我希望稍后能将其增加到更大的数字。

所以我的问题或我需要的帮助是针对这个问题的优化。我确信每个数字仍需要很长时间来检查，但即使是最小百分比的优化也会有很大帮助。

编辑1:优化使用哪些分区编号。理想情况下，这个 除数只能是质数。

这是代码:

#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);

    }
}

Answer 1

很高兴看到您正在研究我几个月前思考的同一问题。 请引用question posted in Math Stackexchange以获得更好的资源。

TL-DR，
您要查找的号码名为SmarandachePrime .

根据您的代码，您似乎正在除以不是 2,5 倍数的每个数字。要优化，您实际上可以检查 n = 6k+1 ( 𝑘 ∈ ℕ )。 不幸的是，就您正在处理的数量而言，这仍然不是更好的方法。

更好的方法是使用素性测试筛选来查找序列中可能的素数，然后检查它们是否是素数。这些测试花费的时间更少~(O(k log3n))与除法相比，使用数学基础知识来检查一个数字是否是质数。
有几个库提供素性检查函数。
对于 python，您可以使用 gmpy2 库，它使用 Miller-Rabin Primality test寻找可能的素数。

我建议您进一步阅读不同的Primality tests在这里。