n8118's blog

By n8118, history, 4 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by n8118 (previous revision, new revision, compare).

»
4 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;
}

  • »
    »
    4 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

  • »
    »
    4 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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In your code in the link "C++ Code with comments"

      In the last loop what is the significance of taking int x=max(A/p,2)

      Please explain. Thanks in advance.

      The last loop is this down below.

      for(int p : P)
              {
                  int x = max(A/p,2);
                  for(int k = p*x; k <= B; k += p) NP.insert(k);
              }
      
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think my code is same as yours and runs on my ide perfectly but on spoj I get wrong answer Please help to point out the mistake if any

    include<stdio.h>

    include<math.h>

    void check(long long int n) { int i,j; if(n==1) { return; } for(i=2;i<sqrt(n);i++) { if(n%i==0) return; } printf("%lld\n",n); return; }

    int main() { int t,i; long long int m,n,j; scanf("%d",&t); for(i=0;i<t;i++) {

    scanf("%lld %lld",&m,&n);
        printf("\n");
        for(j=m;j<n+1;j++)
        {
    
            check(j);
        }
    }

    }