Getting result 1 less or 1 more, divisor counting Program - C

Question

I'm solving a problem.
Problem Link:

http://www.codechef.com/NOV13/problems/PRETNUM

The Problem is about counting the numbers having their divisor count prime (numbers having their number of divisors prime) in the given range of L and R. 1<=L<=R<=10^12 and L-R<=10^6

My code gives correct output for input less than 10^10. But for numbers greater than 10^10, the answer is either 1 less or 1 greater than correct answer. I'm not able to figure out what the problem might be. My Solution:

/*
*   Problem link: http://www.codechef.com/NOV13/problems/PRETNUM
*   Approach: Using Segmented Sieve to generate primes, and counting divisors
*             for perfect squares.
*   Abhishek Kannojia
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PLIMIT 78500
#define NLIMIT 1000000
typedef unsigned long long int  ull;

int primes[PLIMIT], maxp;


//Precomputing Pirmes upto 10^6
int precompute() {
unsigned long i, j, k;
int *numbers;

numbers=(int *)malloc(sizeof(int)*NLIMIT+2);

    for(i=2; i<NLIMIT; i++)
        numbers[i]=1;

    //Sieving Primes
    for(i=2; i<=NLIMIT; i++) {
        if(numbers[i]) {
                for (j=i+i;j<=NLIMIT;j+=i) {
                numbers[j]=0;
            }
        }
    }
    k=0;//printf("\nGenerated Prime:\n");
    for(i=2; i<NLIMIT; i++)
        if(numbers[i]) {primes[k++]=i; /*printf("%d\n",i);*/}

    free(numbers);

    return k;
}

int isprime(int n)
{
 int i=0;
 if(n==0) return 0;
 for(i=0; i<=maxp; i++) {
    if(primes[i]==n) return 1;
 }
 return 0;
}

// Counting Number of Divisors based on the fact that
// if prime factorisation of n = (p)^a * (q)^b * (r)^c
// then number of divisors will be (a+1)*(b+1)*(c+1)

int divcount(ull num)
{
 int i=0, count=1, n, power;

 if(num==1) return 0;
 while(num>1 && i<maxp) {
   n=primes[i];
   power=0;
   while(num%n==0) {
     num /= n;
     power++;
   }
   count = count*(power+1);
   i++;
 }

//
//  This case handles when on of the prime factor is greater than 10^6
//  which does not fall in precomputed array. But we are sure that only
//  one such prime exists for (n<10^12). So we mulitply result by (1+1)
//

 if(num>1) count*=2;
 return count;
}

int calculate(ull l, ull r)
{
  int i, j, k, n, m, count=0, *numbers;
  ull p;

  m=ceil(sqrt(l));
  n=floor(sqrt(r));

    // If l and r less than 10^6. Directly count from precomputed array.
    // The count of divisor is only checked for perfect squares.

  if(r<=NLIMIT) {
    for(i=0; primes[i]<=r; i++) {
        if(primes[i]>=l) count++;
    }
    while(m<=n) {
        if(isprime(divcount(m*m))) count++;
        m++;
    }
  }
  else {
    for(i=0; i<maxp; i++) if(primes[i]>=l) count++;

    for(i=0; i<maxp;) if(primes[i++]>=r) break;
    k=i;

    // Sieving primes Using Segmented Sieve

    numbers = (int *)malloc(sizeof(int)*(r-l+1));

    i=0;
    for(p=l; p<=r; p++) numbers[i++]=1;
    n=i;

    for(i=0; i<k; i++) {
        if(l%primes[i]==0) j=0;
        else j=primes[i]-(l%primes[i]);
            for(;j<n; j+=primes[i]) {
                if(numbers[j]) {
                    numbers[j]=0;
                }
            }

    }
    for(i=0; i<n; i++)
       if(numbers[i]) count++;

    n=sqrt(r);
    while(m<=n) {
        if(isprime(divcount(m*m))==1) count++;
        m++;
    }
 }
 return count;
}

int main(){

    int tc, i, c;
    ull l, r;
    maxp=precompute();
    scanf("%d",&tc);
    while(tc--)
    {
        scanf("%llu %llu",&l,&r);

    c=calculate(l,r);
    printf("%d\n",c);
    }
  return 0;
}

My approach is to first count all primes in given range(Since they have divisor count of 2, which is prime) and then checking divisor count of perfect squares in range because only perfect squares can have prime divisor count.

To count the primes I used Segmented Sieve Approach. To count the divisors for perfect squares I used the fact that if a number N having prime factorisation N = (p)^a * (q)^b * (r)^c then number of divisors for N will be (a+1)(b+1)(c+1) [https://stackoverflow.com/a/110365 ]

Can Anyone help me with this..

Your question isn't really a question; it's just a plea for help, which isn't a good fit for Stack Overflow. And please post your code here rather than links to it which will likely decay over time. — Carey Gregory, Nov 19 '13 at 05:50

score 1 · Answer 1 · answered Nov 19 '13 at 05:48

1

You are using unsigned long type. It is not big enough for 10^10. Unsigned long is from 0 to 4294967295 (2^32 - 1). It is less than 5 * 10^9. So you have to use bigger internal type (64 bit) or long arithmetic (your own implementation of integer data type).

answered Nov 19 '13 at 05:48

Ilya

4,583
4
26
51

I don't think it's datatype problem. I used unsigned long only for precomputing primes below 10^6. Otherwise I have used unsigned long long type – abhishekkannojia Nov 19 '13 at 06:05
Ok, it sounds logical. But have you tried to replace all 'int's and 'unsignet int's with 'ull'? Please confirm, that problem still exists if all your integer types are 64bit. – Ilya Nov 19 '13 at 07:30
1

ok, i got the problem, it's a datatype problem, I used the int type variables m and n to store the square root of the numbers, where number itself can be 10^12. So I used unsigned long. However I still don't understand is int in gcc is not sufficient to store 10^6. I thought on 32bit machines range of int is 2^32 equivalent to 10^9. – abhishekkannojia Nov 19 '13 at 09:26
It depends on compiler options, OS and machine configuration. Read [this help](http://gcc.gnu.org/onlinedocs/gcc/i386-and-x86_002d64-Options.html) (near description of '-m') – Ilya Nov 19 '13 at 09:43

Getting result 1 less or 1 more, divisor counting Program - C

1 Answers1