分段篩eratosthenes spoj Prime1 C++

-7

我一直在努力解決這個問題http://www.spoj.com/problems/PRIME1/，如果任何人都可以幫我找到我的代碼中的錯誤。我使用了eratosthenes的分段篩，我也瀏覽了大量的在線資源，但不知何故，我得到了關於spoj的運行時錯誤。感謝分段篩eratosthenes spoj Prime1 C++

#include <iostream> 
    #include <cstdio> 
    #include <algorithm> 
    #include <vector> 
    #include <string> 
    #include <cmath> 
    #include <map> 
    #include <cstdlib> 
    #include <cassert> 
    #define fora(i,a,b) for(i = a; i < b; i++) 
    #define fin(f) freopen(f, "r", stdin) 
    #define fout(f) freopen(f, "w", stdout) 
    using namespace std; 

typedef long long ll; 
typedef vector<int> vi; 
typedef vector<vi> vii; 
typedef vector<ll> vll; 
typedef vector<bool> vb; 

const ll LIMIT = 1000000000; 

void segmentedSieve(ll n, ll m, int segment_size) { 
    int i, j, s, p, range; 
    vb is_prime(range+1, true); 
    vb seg_primes(segment_size+1, true); 
    vi prime; 

    range = floor(sqrt((double)n)); 

    fora (i, 2, range+1) 
     if (is_prime[i]) { 
      for (j = i*2; j <= range; j+=i) 
       is_prime[j] = false; 
     } 

    fora (i, 2, range+1) 
     if (is_prime[i] == 1) 
      prime.push_back(i); 

    fora (i, 0, prime.size()) { 
     p = prime[i]; 
     s = m/p; 
     s *= p; 

     for (j = s; j <= n; j+=p) { 
      if (j < m) continue; 
      seg_primes[j-m] = false; 
     } 
    } 

    fora (i, 0, prime.size()) 
     if (prime[i] >= m && prime[i] <= n) { 
      cout << prime[i] << endl; 
     } 

    fora (i, 0, n-m+1) 
     if (seg_primes[i] && (i+m) != 1) { 
      cout << i+m << endl; 
     } 
} 

int main() 
{ 
    int segment_size = 100000; 
    // fin("input.in"); 
    int t; 
    cin >> t; 
    while (t--) { 
     ll a, b; 
     cin >> a >> b; 
     if (a > b) 
      segmentedSieve(a, b, segment_size); 
     else 
      segmentedSieve(b, a, segment_size); 
     if (t != 0) 
      cout << endl; 
    } 
}

來源

2016-01-02 Bhavya Jain

現在是學習使用調試器的時候了。（並且幫你一個忙，刪除這些宏，它們太可怕了。） – Mat

那些宏除了混淆代碼之外什麼都不會給你買。沒有必要有一個定義'for'循環的宏 - 我們都知道'for'循環的樣子。我們都知道'long long'是什麼，等等。我同意Mat，他們很可怕。至於'long long'，我幾天前看到另一個SPOJ的帖子使用了相同的可怕宏。 SPOJ教你如何使用它？ – PaulMcKenzie

哈哈哈......只是幫助我們更快地編寫一點律：P –

看來range未初始化的位置：

void segmentedSieve(ll n, ll m, int segment_size) { 
    int i, j, s, p, range; 
    vb is_prime(range+1, true); // uninitialized range... !!

也許你想

void segmentedSieve(ll n, ll m, int segment_size) { 
    int i, j, s, p, range; 

    range = floor(sqrt((double)n)); // This first... 

    vb is_prime(range+1, true);  // then this

如果可能的話，當你確定你應該如何初始化變量。

void segmentedSieve(ll n, ll m, int segment_size) { 
    int i, j, s, p; // no range here 

    int range = floor(sqrt((double)n)); // This first... 

    vb is_prime(range+1, true);  // then this

一般來說，你應該推遲變量的定義，直到你需要它們，即不要在開始定義的所有變量，但做到這一點，你需要他們。

p.s.正如其他人已經評論 - 擺脫所有宏觀的東西...

來源

2016-01-02 08:52:20 4386427

非常感謝您......而且耶也會擺脫這些宏 –

分段篩eratosthenes spoj Prime1 C++

回答

相關問題