JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions Spoj n-divisors (NDIV)
 Spoj n-divisors (NDIV) | Reply Hello , I was trying to solve this problem (http://www.spoj.com/problems/NDIV/) first I faced some TLE but then WA any help would be appreciated here is my code :```#include #include #include #include using namespace std; bool prime[100001]; int primes[100001]; int maxPrime; int x = 0;   void sieve(int till) { x = sqrt(till) + 1; int c = 0; for(int i = 2; i <= x;i++) { if(!prime[i]) { maxPrime = c+1; primes[c++] = i; for(int j = i*i;j <= x;j+=i) { prime[j] = true; } } } }   int main() { int arr[100001]; int div[100001]; int left , right , wanted; while(cin >> left) { cin >> right >> wanted; sieve(right); for (int i = left; i <= right; i++) { div[i - left] = 1; arr[i - left] = i; } for(int i = 0;i < maxPrime;i++) { int p = primes[i]; int first = left; if(left%p > 0) first = (left/p +(left%p))*p; for (int k = first; k <= right; k += p) { int c = 1; while (arr[k - left] % p == 0) { arr[k - left] /= p; c++; } div[k - left] *= c; } } int result = 0; for (int i = left; i <= right; i++) { if (arr[i - left] > 1) div[i - left] *= 2; if(div[i-left] == wanted) result++; } printf("%d\n",result); } } ```
 Re: Spoj n-divisors (NDIV) (response to post by Abdelrahman2012) | Reply Some suggestion :1.Try sieve only one time up to MAX sieve all primes till 32000. I think you are getting TLE because you are finding primes in every test case try to avoid this.
 Re: Spoj n-divisors (NDIV) (response to post by Luckymaster) | Reply Why till 32000, when the max number is 10^9. Can't there be a prime greater than 32000 ?
 Forums Round Tables External Competitions Spoj n-divisors (NDIV) Previous Thread  |  Next Thread