Блог пользователя n8118

Spoj problem Prime1(segmented sieve)
Автор n8118, история, 11 лет назад, По-английски

I have been trying to solve a problem on segmented sieve i.e prime1(http://www.spoj.com/problems/PRIME1/) in spoj but i am getting wrong answer and unable to find the bug in the code. So please help me..

http://ideone.com/JiSxel

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Sieve Of Eratosthenes will give TLE. It works only for numbers <= 10^6, maybe <= 10^7 with complexity O(n*ln(ln(n))). While checking if number is prime works with numbers <= 10^12 with complexity O(sqrt(n)).

#include <stdio.h>

bool isPrime(int n) {
  if (n == 1) {
    return false;
  }
  int d = 2;
  while (d * d <= n) {
    if (n % d == 0) {
      return false;
    }
    d++;
  }
  return true;
}

int main() {
  int t, m, n;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &m, &n);
    for(int i = m; i <= n; i++) {
      if(isPrime(i)) printf("%d\n", i);
    }
  }
  return 0;
}
→ Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    If there are 10 test cases, with worst case of n — m = 100000

    worst complexity will be 100000 * 10 * sqrt(1000000000). it would surely tle

    reply to sbakic

    → Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
    ← Rev. 4  
    Проголосовать: нравится 0 Проголосовать: не нравится

    This will give TLE too. You're doing 105 * log109 operations, which is over 3000M operations.

    The correct solution is to generate a list of prime numbers beforehand, and then mark non-prime numbers in the range [A, B] (if a number is not prime, then there is a prime less or equal than its square root that divides it).

    Here's the code: C++ Code with comments

    UPDATE: Your solution was OK, albeit slower because it uses map instead of unordered_map. You only needed to consider that l is not prime if l divides p and l > p. Your program didn't consider this last condition and didn't print 2 when l = 2.

    → Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I think this problem should be solved using segmented sieve algorithm. :)

→ Ответить