2

我正在尝试解决这个问题http://www.urionlinejudge.com.br/judge/problems/view/1032，我需要以最快的方式找到 1 到 3501 之间的质数，因为时间限制可能不会超过 1 秒。

我计算这些素数的方法是检查它们是否是素数直到它们的平方根，然后消除第一个素数的倍数 [2, 3, 5, 7] 以提高算法的性能。然而，时间超过了。

我的代码（提交系统内测用了1.560s）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <set>

using namespace std;

set<int> circ;
set<int> primes;

/* Calculate List Primes */ 
void n_prime(int qtd){
    int a, flag=1, l_prime = 1;
    float n;
    for(int i=0;i<qtd;i++){
        switch (l_prime){
            case 1:
                l_prime = 2;
                break;
            case 2:
                l_prime = 3;
                break;
            default:
                while(1){
                    flag=1;
                    l_prime+=2;
                    if(l_prime>7)
                    while(l_prime%2==0||l_prime%3==0||l_prime%5==0||l_prime%7==0) l_prime++;
                    n=sqrt(l_prime);
                    for(a=2;a<=n;a++){
                        if(l_prime%a==0){
                            flag=0;
                            break;
                        }
                    }
                    if(flag) break;
                }
        }
        primes.insert(l_prime);
    }
}

/* Initialize set with live's */ 
void init_circ(int t){
    circ.clear();
    for(int a=0;a<t;a++){
        circ.insert(a+1);
    }
}

/* Show last live*/
void show_last(){
    for(set<int>::iterator it=circ.begin(); it!=circ.end(); ++it)
        cout << *it << "\n";
}

int main(){
    int n = 0;
    clock_t c1, c2;
    c1 = clock();
    n_prime(3501);
    while(scanf("%d", &n)&&n!=0){
        init_circ(n);
        int idx=0, l_prime,count = 0;
        set<int>::iterator it;
        set<int>::iterator np;
        np=primes.begin();
        for(int i=0;i<n-1;i++){
            l_prime=*np;
            *np++;
            idx = (idx+l_prime-1) % circ.size();
            it = circ.begin();
            advance(it, idx);
            circ.erase(it);
        }
        show_last();
    }
    c2 = clock();
    printf("\n\nTime: %.3lf", (double)(c2-c1)/CLOCKS_PER_SEC);
    return 0;
}
4

6 回答 6

4

最简单的方法是Eratosthenes 的筛子，这是我的实现： 

//return the seive of erstothenes
std::vector<int> generate_seive(const ulong & max) {
    std::vector<int> seive{2};
    std::vector<bool> not_prime(max+1);
    ulong current_prime = seive.back();
    bool done = false;
    while(!done){ 
        for (int i = 2; i * current_prime <= max;i++) {
            not_prime[i*current_prime]=true;
        }
        for (int j = current_prime+1;true;j++) {
            if (not_prime[j] == false) {
                if( j >= max) {
                    done = true;
                    break;
                }
                else {
                    seive.push_back(j);
                    current_prime = j;
                    break;
                }
            }
        }
    }
    return seive;
}

生成最大值下的所有素数，顺便说一句，这些是我的筛子的时间，3501 作为最大数。 

real    0m0.008s
user    0m0.002s
sys     0m0.002s
于 2013-08-29T19:03:25.610 回答
2

有一个更好的算法来寻找素数。你听说过Eratosthenes 和他的筛子吗？

此外，您在代码中使用了大量的 STL（即 set<>）以及余数操作。这只是在扼杀程序的速度。

于 2013-08-29T19:03:48.407 回答
1

一些基本建议，然后是基本（尽管未经测试）答案......

建议：如果您的一种资源非常有限，请利用其他资源。在这种情况下，由于时间有限，占用了大量空间。不要动态分配任何内存，将其全部设为固定长度数组。

我这样做的方法就是拥有一个布尔数组并将 Aristophanes 的筛子应用于它：

void findPrimes(int cap) { // set to void for now, since I don't know your return type
    bool[] possibilities = new bool[cap + 1]; // has to be dynamic so that you can scale for any top
    possibilities[0] = false;
    possibilities[1] = false;
    int found = 0;

    for (int i = 2; i < cap; ) {
        ++found;
        for (int j = i + i; j < cap; j += i) {
            possibilities[j] = false;
        }
        do {
            ++i;
        } while (!possibilities[i]);
    }

    // at this point, found says how many you've found, and everything in possibilities that is true is a factor.  Just return it however you need.

我看到 aaronman 用筛子的想法打败了我。我的实现略有不同（更类似于原始筛子，仅使用加法），并且使用较少的动态内存，所以我仍在提交它。

于 2013-08-29T19:12:18.210 回答
0

正如其他人所建议的那样，Eratosthenes 的筛子是正确的方法。但是我在这里看到的实现非常复杂。筛子非常容易实施。例如：

std::vector<int> get_primes(uint max) {
  std::vector<int> primes;
  std::vector<bool> is_composite(max+1,false);
  for (uint i = 2; i <= max; ++i) {
    if (!is_composite[i]) {
      primes.push_back(i);
      for (uint j = i+i; j <= max; j += i) {
        is_composite[j] = true;
      }
    }
  }
  return primes;
}
于 2013-08-29T19:17:04.097 回答
0

您可以通过预先排除偶数来获得相当不错的加速，只需将您的增量更改为i += 2并确保您没有在结果数组中省略 2。您甚至可能考虑尝试预先排除 3 的倍数，但这开始变得很糟糕。类似的东西：

for(long i = 1; i < qtd; i += 6) {
    //check if i is prime
    //check if i+4 is prime
}

这应该足以让您低于限制。

于 2013-08-29T19:12:42.233 回答
0

您的代码中有两个大的技术性能消耗：

  1. 您将素数插入向量中。每当向量超过其分配的大小时，它将获得一个新的、更大的缓冲区，复制所有内容，并删除旧的。new在性能方面非常昂贵，甚至比涉及的复制还要昂贵。reserve()您可以通过告诉向量有足够的空间来避免这种情况。

  2. 您sqrt()在内部循环中使用。这也是一个缓慢的功能，取而代之的是平方素数（在现代硬件上只需要一个周期），它会更快。

于 2013-08-29T19:30:32.957 回答