n8118's blog

By n8118, history, 4 years ago, , 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 spoj, Comments (6)
 » Auto comment: topic has been updated by n8118 (previous revision, new revision, compare).
 » 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 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 →   If there are 10 test cases, with worst case of n — m = 100000worst complexity will be 100000 * 10 * sqrt(1000000000). it would surely tlereply to sbakic
•  » » 4 years ago, # ^ | ← Rev. 4 →   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 commentsUPDATE: 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.
•  » » » 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); }
• »
»

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<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);
}
}

}