n8118's blog

Spoj problem Prime1(segmented sieve)
By n8118, history, 9 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply