所以我的靈感來自于最近來自 Numberphile 頻道的 Youtube 視頻。準確的說是這個。對于我所指的確切問題或示例，將其縮短到 5 分鐘左右。
TLDR；創建一個數字，其中所有數字都對應于1 到N。示例：1 到 10 是數字 12,345,678,910。找出這個數字是否是素數。根據視頻，N已被檢查到1,000,000。
從下面的代碼中，我冒昧地從 1,000,000 開始這個程序，然后只到 10,000,000。我希望稍后將其增加到更大的數字。
所以我的問題或我需要的幫助是優化這個問題。我確信每個數字仍然需要很長時間來檢查，但即使是最小百分比的優化也會有很長的路要走。
編輯 1：優化使用的磁區編號。理想情況下，這個 DivisionNumber 只會是素數。
這是代碼：
#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);
}
}
uj5u.com熱心網友回復：
很高興看到您正在研究我幾個月前思考的同一問題。請參閱Math Stackexchange 中發布的問題以獲得更好的資源。
TL-DR，
您要查找的號碼稱為SmarandachePrime。
根據您的代碼，您似乎正在除以每個不是 2,5 倍數的數字。為了優化，您實際上可以檢查 n = 6k 1 ( ?? ∈ ? )。不幸的是，就您要處理的數字而言，這仍然不是更好的方法。
更好的方法是使用素性檢驗篩選，找出序列中可能的素數，然后檢查它們是否是素數。與除法相比，這些測驗使用數學基礎來檢查一個數是否為素數所需的時間更短~(O(k log3n))。
有幾個庫提供素數檢查功能。
對于 python，您可以使用 gmpy2 庫，它使用Miller-Rabin Primality 測驗來查找可能的素數。
我建議您在此處進一步閱讀不同的Primality 測驗。
uj5u.com熱心網友回復：
我相信您遺漏了一項非常重要的檢查，即除以 3：
一個數能被3整除就是能被3整除的數之和，你的數由1到N的所有陣列成。1到N
的數之和等于：
N * (N 1) / 2
這意味著，如果 N 或 N 1 可以被 3 整除，那么您的數字就不能是質數。
所以在你做任何事情之前，檢查MOD(N,3)和MOD(N 1,3)。如果其中任何一個為零，則不能有質數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/384822.html