2

私はこの問題http://www.urionlinejudge.com.br/judge/problems/view/1032を理解しようとしています.1から3501までの素数を最速の方法で見つける必要があります. 1 秒を超えます。

これらの素数を計算する方法は、平方根まで素数であるかどうかを確認し、最初の素数 [2, 3, 5, 7] の倍数を削除して、アルゴリズムのパフォーマンスを向上させることです。それでも時は過ぎていく。

私のコード (提出システムの内部テストとして 1.560 秒かかります)

#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

素数を見つけるためのより良いアルゴリズムがあります。エラトステネスと彼のふるいについて聞いたことがありますか?

また、大量の STL (つまり set<>) とコード内の剰余演算を使用しています。これは単にプログラムの速度を落としています。

于 2013-08-29T19:03:48.407 に答える
1

いくつかの基本的なアドバイス、そして基本的な（テストされていませんが）答え...

アドバイス: 1 つのリソースが非常に限られている場合は、他のリソースを活用してください。この場合、時間が限られているため、多くのスペースを占有します。メモリを動的に割り当てず、すべて固定長の配列にします。

私がそれを行う方法は、1つのブール配列を持ち、それにアリストファネスのふるいを適用することです:

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.

アーロンマンがふるいのアイデアで私を打ちのめしたのを見ました。私の実装はわずかに異なり (加算のみを使用して、元の sieve とより正確に似ています)、使用する動的メモリが少ないため、引き続き提出します。

于 2013-08-29T19:12:18.210 に答える
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

コードには、2 つの大きな技術的パフォーマンスの低下があります。

  1. 素数をベクトルに挿入します。ベクトルが割り当てられたサイズを超えると、新しい大きなバッファが取得され、すべてがコピーされ、古いバッファが削除されます。newパフォーマンスの点で非常に高価であり、関連するコピーよりもさらに高価です。reserve()ベクトルに十分なスペースを指定することで、これを回避できます。

  2. sqrt()内側のループで使用します。これも遅い関数で、代わりに素数を 2 乗します (最新のハードウェアでは 1 サイクルしかかかりません)。より高速になります。

于 2013-08-29T19:30:32.957 に答える