时间戳

首页 > 解决方案 > 如何减少这个程序的时间？

c++ - 如何减少这个程序的时间？

问题描述

我有一个这样的程序：给定一个整数序列，找到最大的素数及其位置。

例子：

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 << ' ';
    }
}

标签： c++performancec++11timeprimes

解决方案

如果您需要最大的素数，那么对数组进行排序不会给您带来任何好处，无论如何您都需要检查存储在数组中的所有值。

即使您实现了快速排序算法，您希望得到的最佳平均值也是O(N + k)，因此仅对数组进行排序实际上比在未排序数组中寻找最大素数的成本更高。

这个过程非常简单，检查下一个值是否大于当前最大的素数，如果是，检查它是否也是素数，如果是，则存储位置和/或值，如果不是，检查下一个值，重复直到数组的末尾。

θ(N)给定条件，时间复杂性将是可能的最佳优化。

推荐阅读