如何减少这个程序的时间？
How to reduce the time in this program?
我有这样一个程序：给定一个整数序列，找到最大的素数及其位置。
示例：
input:
9 // how many numbers
19 7 81 33 17 4 19 21 13
output:
19 // the biggest prime
1 7 // and its positon
所以首先我得到输入，将它存储在一个数组中，制作该数组的副本并对其进行排序（因为我使用变量来跟踪最高素数，如果未排序就会发生疯狂的事情) 使用该数组的每个数字来检查它是否是质数，再次循环它以获得位置并打印结果。
但是时间太慢了，可以改进吗？
我的代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int numbersNotSorted[n];
int maxNum{0};
for (int i = 0; i < n; i++)
{
cin >> numbersNotSorted[i];
}
int numbersSorted[n];
for (int i = 0; i < n; i++)
{
numbersSorted[i] = numbersNotSorted[i];
}
sort(numbersSorted, numbersSorted + n);
for (int number = 0; number < n; number++)
{
int countNum{0};
for (int i = 2; i <= sqrt(numbersSorted[number]); i++)
{
if (numbersSorted[number] % i == 0)
countNum++;
}
if (countNum == 0)
{
maxNum = numbersSorted[number];
}
}
cout << maxNum << '\n';
for (int i = 0; i < n; i++)
{
if (numbersNotSorted[i] == maxNum)
cout << i + 1 << ' ';
}
}
如果您需要最大素数，则对数组进行排序没有任何好处，无论如何您都需要检查存储在数组中的所有值。
即使您实现了快速排序算法，the best averages you can hope for are O(N + k)，所以仅对数组进行排序实际上比在未排序的数组中查找最大素数的成本更高。
这个过程非常简单，检查下一个值是否大于当前最大的素数，如果是，则检查它是否也是素数，如果是，则存储位置 and/or 值，如果不是，检查下一个值，重复直到数组末尾。
θ(N) 时间复杂度将是给定条件下可能的最佳优化。
从基本的“输入每个数字”循环开始：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
int n;
int newNumber;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
}
}
如果新数小于当前最大质数，则可以忽略。
int main() {
int n;
int newNumber;
int highestPrime;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
if(newNumber >= highestPrime) {
}
}
}
如果新数等于最高质数，那么你只需要将它的位置存储在某个地方。我很懒，所以:
int main() {
int n;
int newNumber;
int highestPrime;
int maxPositions = 1234;
int positionList[maxPositions];
int nextPosition;
int currentPosition = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
currentPosition++;
if(newNumber >= highestPrime) {
if(newNumber == highestPrime) {
if(nextPosition+1 >= maxPositions) {
// List of positions is too small (should've used malloc/realloc instead of being lazy)!
} else {
positionList[nextPosition++] = currentPosition;
}
}
}
}
}
如果新数大于当前最大素数，则需要判断是否为素数，如果是则需要重置链表并存储其位置等:
int main() {
int n;
int newNumber;
int highestPrime = 0;
int maxPositions = 1234;
int positionList[maxPositions];
int nextPosition;
int currentPosition = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
currentPosition++;
if(newNumber >= highestPrime) {
if(newNumber == highestPrime) {
if(nextPosition+1 >= maxPositions) {
// List of positions is too small (should've used malloc/realloc instead of being lazy)!
} else {
positionList[nextPosition++] = currentPosition;
}
} else { // newNumber > highestPrime
if(isPrime(newNumber)) {
nextPosition = 0; // Reset the list
highestPrime = newNumber;
positionList[nextPosition++] = currentPosition;
}
}
}
}
}
您还需要一些东西来显示结果：
if(highestPrime > 0) {
for(nextPosition= 0; nextPosition < currentPosition; nextPosition++) {
cout << positionList[nextPosition];
}
}
现在；您唯一缺少的是 isPrime(int n) 函数。最快的方法是 pre-calculate 一个“is/isn't prime”位域。它可能看起来像：
bool isPrime(int n) {
if(n & 1 != 0) {
n >>= 1;
if( primeNumberBitfield[n / 32] & (1 << (n % 32)) != 0) {
return true;
}
}
return false;
}
这里的问题是（对于 32 位带符号整数中的正值）您需要 10 亿位（或 128 MiB）。
为避免这种情况，您可以为最大 sqrt(1 << 31)（仅约 4 KiB）的数字使用更小的位域；然后，如果数字对于位域来说太大，您可以使用位域查找素数并检查（使用模数）它们是否将原始数字平均划分。
请注意，Eratosthenes 筛法 (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 是生成较小位域的有效方法（但对于较大数量的稀疏总体而言效率不高）。
如果你做对了，你可能会产生它是瞬时的错觉，因为几乎所有的工作都将在一个人慢慢输入数字时完成（直到所有数字都输入完毕后才离开）被输入）。对于速度非常快的打字员，数字之间的间隔约为 2 毫秒，并且（在输入最后一个数字后）人类无法注意到小于 10 毫秒的延迟。
But the time is too slow, can I improve it?
下面的循环有：
为什么要先检查最小值？首先检查最大值以找到最大素数更有意义。找到质数后，尽早退出 for (... number..) 循环。这利用了 sort().
所做的工作
一旦候选值不是素数，就停止对 prime-ness 的测试。
.
// (1) Start for other end rather than as below
for (int number = 0; number < n; number++) {
int countNum {0};
for (int i = 2; i <= sqrt(numbersSorted[number]); i++) {
if (numbersSorted[number] % i == 0)
// (2) No point in continuing prime testing, Value is composite.
countNum++;
}
if (countNum == 0) {
maxNum = numbersSorted[number];
}
}
留给 OP 实施的更正。
- 高级：Prime 测试是一个很深的主题，存在许多比 OP 方法更好的优化（琐碎的和复杂的）。但我怀疑上述 2 个改进对 OP 来说已经足够了。
脆弱性：代码不能很好地处理列表中没有素数的情况或n <= 0。
i <= sqrt(numbersSorted[number]) 容易出现导致错误结果的 FP 问题。推荐i <= numbersSorted[number]/i).
排序是 O(n * log n)。此处进行的主要测试是 O(n * sqrt(n[i]))。当最大值的平方根小于 n 的 log 时，排序不会增加整体代码 O()。排序的结果用得好，排序也是值得的
如果最大值为 1，则代码失败，因为素数测试错误地将 1 识别为素数。
如果 numbersSorted[number] < 0 由于 sqrt()，代码失败。
简单full-range int素数测试：
bool isprime(int num) {
if (num % 2 == 0) return num == 2;
for (int divisor = 3; divisor <= num / divisor; divisor += 2) {
if (num % divisor == 0) return false;
}
return num > 1;
}
如果你想找到质数，就不要去排序。然后你必须检查数组中存在的所有数字。
您可以尝试使用这种方法来完成同样的事情，但会在更短的时间内完成：
Step-1: 创建一个 global 函数来检测素数。以下是您可以如何处理这个问题-
bool prime(int n)
{
int i, p=1;
for(i=2;i<=sqrt(n);i++) //note that I've iterated till the square root of n, to cut down on the computational time
{
if(n%i==0)
{
p=0;
break;
}
}
if(p==0)
return false;
else
return true;
}
第 2 步： 现在您的主要功能开始了。您从用户那里获取输入：
int main()
{
int n, i, MAX;
cout<<"Enter the number of elements: ";
cin>>n;
int arr[n];
cout<<"Enter the array elements: ";
for(i=0;i<n;i++)
cin>>arr[i];
步骤 3： 请注意，我已经声明了一个计数器变量 MAX。我将此变量初始化为数组的第一个元素：MAX=arr[0];
Step-4: 现在是迭代数组的循环。我所做的是，我遍历数组并在每个元素处检查值是否大于或等于前一个 MAX。这将确保程序不会检查小于 MAX 的值，从而消除数组的一部分并缩短时间。然后我嵌套了另一个 if 语句，以检查该值是否为素数。如果这两个都满足，我把MAX的值设置为数组的当前值：
for(i=0;i<n;i++)
{
if(arr[i]>=MAX) //this will check if the number is greater than the previous MAX number or not
{
if(prime(arr[i])) //if the previous condition satisfies, then only this block of code will run and check if it's a prime or not
MAX=arr[i];
}
}
这是怎么回事- MAX 的值在每个循环.
后变为数组的最大质数
Step-5: 然后，最后遍历数组后，当程序最终跳出循环时，MAX将得到最大的素数数组存储在其中。打印 MAX 的这个值。现在为了获得 MAX 发生的位置，只需遍历整个循环并检查匹配 MAX 的值并打印它们的位置：
for(i=0;i<n;i++)
{
if(arr[i]==MAX)
cout<<i+1<<" ";
}
我运行这段代码在Dev C++ 5.11编译时间是0.72s.
我有这样一个程序：给定一个整数序列，找到最大的素数及其位置。
示例：
input:
9 // how many numbers
19 7 81 33 17 4 19 21 13
output:
19 // the biggest prime
1 7 // and its positon
所以首先我得到输入，将它存储在一个数组中，制作该数组的副本并对其进行排序（因为我使用变量来跟踪最高素数，如果未排序就会发生疯狂的事情) 使用该数组的每个数字来检查它是否是质数，再次循环它以获得位置并打印结果。
但是时间太慢了，可以改进吗？
我的代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int numbersNotSorted[n];
int maxNum{0};
for (int i = 0; i < n; i++)
{
cin >> numbersNotSorted[i];
}
int numbersSorted[n];
for (int i = 0; i < n; i++)
{
numbersSorted[i] = numbersNotSorted[i];
}
sort(numbersSorted, numbersSorted + n);
for (int number = 0; number < n; number++)
{
int countNum{0};
for (int i = 2; i <= sqrt(numbersSorted[number]); i++)
{
if (numbersSorted[number] % i == 0)
countNum++;
}
if (countNum == 0)
{
maxNum = numbersSorted[number];
}
}
cout << maxNum << '\n';
for (int i = 0; i < n; i++)
{
if (numbersNotSorted[i] == maxNum)
cout << i + 1 << ' ';
}
}
如果您需要最大素数，则对数组进行排序没有任何好处，无论如何您都需要检查存储在数组中的所有值。
即使您实现了快速排序算法，the best averages you can hope for are O(N + k)，所以仅对数组进行排序实际上比在未排序的数组中查找最大素数的成本更高。
这个过程非常简单，检查下一个值是否大于当前最大的素数，如果是，则检查它是否也是素数，如果是，则存储位置 and/or 值，如果不是，检查下一个值，重复直到数组末尾。
θ(N) 时间复杂度将是给定条件下可能的最佳优化。
从基本的“输入每个数字”循环开始：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
int n;
int newNumber;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
}
}
如果新数小于当前最大质数，则可以忽略。
int main() {
int n;
int newNumber;
int highestPrime;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
if(newNumber >= highestPrime) {
}
}
}
如果新数等于最高质数，那么你只需要将它的位置存储在某个地方。我很懒，所以:
int main() {
int n;
int newNumber;
int highestPrime;
int maxPositions = 1234;
int positionList[maxPositions];
int nextPosition;
int currentPosition = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
currentPosition++;
if(newNumber >= highestPrime) {
if(newNumber == highestPrime) {
if(nextPosition+1 >= maxPositions) {
// List of positions is too small (should've used malloc/realloc instead of being lazy)!
} else {
positionList[nextPosition++] = currentPosition;
}
}
}
}
}
如果新数大于当前最大素数，则需要判断是否为素数，如果是则需要重置链表并存储其位置等:
int main() {
int n;
int newNumber;
int highestPrime = 0;
int maxPositions = 1234;
int positionList[maxPositions];
int nextPosition;
int currentPosition = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> newNumber;
currentPosition++;
if(newNumber >= highestPrime) {
if(newNumber == highestPrime) {
if(nextPosition+1 >= maxPositions) {
// List of positions is too small (should've used malloc/realloc instead of being lazy)!
} else {
positionList[nextPosition++] = currentPosition;
}
} else { // newNumber > highestPrime
if(isPrime(newNumber)) {
nextPosition = 0; // Reset the list
highestPrime = newNumber;
positionList[nextPosition++] = currentPosition;
}
}
}
}
}
您还需要一些东西来显示结果：
if(highestPrime > 0) {
for(nextPosition= 0; nextPosition < currentPosition; nextPosition++) {
cout << positionList[nextPosition];
}
}
现在；您唯一缺少的是 isPrime(int n) 函数。最快的方法是 pre-calculate 一个“is/isn't prime”位域。它可能看起来像：
bool isPrime(int n) {
if(n & 1 != 0) {
n >>= 1;
if( primeNumberBitfield[n / 32] & (1 << (n % 32)) != 0) {
return true;
}
}
return false;
}
这里的问题是（对于 32 位带符号整数中的正值）您需要 10 亿位（或 128 MiB）。
为避免这种情况，您可以为最大 sqrt(1 << 31)（仅约 4 KiB）的数字使用更小的位域；然后，如果数字对于位域来说太大，您可以使用位域查找素数并检查（使用模数）它们是否将原始数字平均划分。
请注意，Eratosthenes 筛法 (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 是生成较小位域的有效方法（但对于较大数量的稀疏总体而言效率不高）。
如果你做对了，你可能会产生它是瞬时的错觉，因为几乎所有的工作都将在一个人慢慢输入数字时完成（直到所有数字都输入完毕后才离开）被输入）。对于速度非常快的打字员，数字之间的间隔约为 2 毫秒，并且（在输入最后一个数字后）人类无法注意到小于 10 毫秒的延迟。
But the time is too slow, can I improve it?
下面的循环有：
为什么要先检查最小值？首先检查最大值以找到最大素数更有意义。找到质数后，尽早退出
所做的工作for (... number..)循环。这利用了sort().一旦候选值不是素数，就停止对 prime-ness 的测试。
.
// (1) Start for other end rather than as below
for (int number = 0; number < n; number++) {
int countNum {0};
for (int i = 2; i <= sqrt(numbersSorted[number]); i++) {
if (numbersSorted[number] % i == 0)
// (2) No point in continuing prime testing, Value is composite.
countNum++;
}
if (countNum == 0) {
maxNum = numbersSorted[number];
}
}
留给 OP 实施的更正。
- 高级：Prime 测试是一个很深的主题，存在许多比 OP 方法更好的优化（琐碎的和复杂的）。但我怀疑上述 2 个改进对 OP 来说已经足够了。
脆弱性：代码不能很好地处理列表中没有素数的情况或n <= 0。
i <= sqrt(numbersSorted[number]) 容易出现导致错误结果的 FP 问题。推荐i <= numbersSorted[number]/i).
排序是 O(n * log n)。此处进行的主要测试是 O(n * sqrt(n[i]))。当最大值的平方根小于 n 的 log 时，排序不会增加整体代码 O()。排序的结果用得好，排序也是值得的
如果最大值为 1，则代码失败，因为素数测试错误地将 1 识别为素数。
如果 numbersSorted[number] < 0 由于 sqrt()，代码失败。
简单full-range int素数测试：
bool isprime(int num) {
if (num % 2 == 0) return num == 2;
for (int divisor = 3; divisor <= num / divisor; divisor += 2) {
if (num % divisor == 0) return false;
}
return num > 1;
}
如果你想找到质数，就不要去排序。然后你必须检查数组中存在的所有数字。
您可以尝试使用这种方法来完成同样的事情，但会在更短的时间内完成：
Step-1: 创建一个 global 函数来检测素数。以下是您可以如何处理这个问题-
bool prime(int n)
{
int i, p=1;
for(i=2;i<=sqrt(n);i++) //note that I've iterated till the square root of n, to cut down on the computational time
{
if(n%i==0)
{
p=0;
break;
}
}
if(p==0)
return false;
else
return true;
}
第 2 步： 现在您的主要功能开始了。您从用户那里获取输入：
int main()
{
int n, i, MAX;
cout<<"Enter the number of elements: ";
cin>>n;
int arr[n];
cout<<"Enter the array elements: ";
for(i=0;i<n;i++)
cin>>arr[i];
步骤 3： 请注意，我已经声明了一个计数器变量 MAX。我将此变量初始化为数组的第一个元素：MAX=arr[0];
Step-4: 现在是迭代数组的循环。我所做的是，我遍历数组并在每个元素处检查值是否大于或等于前一个 MAX。这将确保程序不会检查小于 MAX 的值，从而消除数组的一部分并缩短时间。然后我嵌套了另一个 if 语句，以检查该值是否为素数。如果这两个都满足，我把MAX的值设置为数组的当前值：
for(i=0;i<n;i++)
{
if(arr[i]>=MAX) //this will check if the number is greater than the previous MAX number or not
{
if(prime(arr[i])) //if the previous condition satisfies, then only this block of code will run and check if it's a prime or not
MAX=arr[i];
}
}
这是怎么回事- MAX 的值在每个循环.
Step-5: 然后，最后遍历数组后，当程序最终跳出循环时，MAX将得到最大的素数数组存储在其中。打印 MAX 的这个值。现在为了获得 MAX 发生的位置，只需遍历整个循环并检查匹配 MAX 的值并打印它们的位置：
for(i=0;i<n;i++)
{
if(arr[i]==MAX)
cout<<i+1<<" ";
}
我运行这段代码在Dev C++ 5.11编译时间是0.72s.