GOOD NUMBERS

• Problem Description

  
  A number is called a square free number if there does not exist a number greater than 1, whose square divides the number evenly/perfectly. For example, number 8 is not a square free number as number 4 (which is square of 2), divides 8. Similarly, number 4 is also not a square free number. However numbers 1, 3, 6 all are square free numbers. 
  
  A number n is called a good number if following properties hold. 
  It is a square free number.
  
  Let s denote the sum of all divisors of n (including non-trivial divisors like 1 and itself). Let c denote the number of prime numbers dividing s. Number c should be a prime number.
  You will enter two numbers L, R, you have to find sum of divisors (including non-trivial) of all the good numbers in the range L to R, both inclusive. 
  Please note that 0 is not considered a prime number.
  
  

• CODING ARENA

• #include <stdio.h>

  #define N 100000

   

  static int factorCount[N+1];

  static long long a[N+1];

  long long sumf(long long n)

  {

      long long i,sum=0;

  for(i=1;i*i<=n;i++)

  {if(n%i==0)

  {sum+=(long long)i;

  if(n/i!=i)

  sum+=(long long)n/i;

      

  }

  }   

  return sum;

  }

  int sqrt(long long  n)

   

      {

   

          if(n==1 || n==2 || n==3)

   

              return 1;

   

          long long i=2;

   

          int cnt=0;

   

          double j=sqrt(n);

   

          while(i<=j)

   

          {

   

              if(cnt==2)

   

                  return 0;

   

              else if(n%i==0)

   

              {

   

                  n=n/i;

   

                  cnt += 1;

   

              }

   

              else

   

              {

   

                  cnt = 0;

   

                  i += 1;

   

              }

   

          }

   

          return 1;

   

      }

   

   

  int isPrime(long long n)

  {

     long long i;

      if (n <= 1)  return 0;

      if (n <= 3)  return 1;

   

     

      if (n%2 == 0 || n%3 == 0) 

      return 0;

   

      for (i=5; i*i<=n; i=i+6)

          if (n%i == 0 || n%(i+2) == 0)

             return 0;

   

      return 1;

  }

   

   

   

  int main(void) 

  {

  long long int i, j;

   

      for (i = 0; i <= N; i++) {

          factorCount[i] = 0;

          a[i]=0;

      }

   

      for (i = 2; i <= N; i++) {

          if (factorCount[i] == 0) {

              for (j = i; j <= N; j += i) {

                  factorCount[j]++;

              }

          }

      }

      for(i=1;i<=20000;i++)

      {

          if(isPrime(factorCount[sumf(i)]) && sfree(i))

          {

              a[i]=sumf(i);

             

          }

          

          

      }

      long long t;

      scanf("%lld",&t);

      while(t--)

      {

          long long l,r,sum=0;

          scanf("%lld %lld",&l,&r);

          for(i=l;i<=r;i++)

          {

              if(a[i]!=0)

              sum=sum+a[i];

          }

          printf("%lld\n",sum);

      }

  return 0;

  }

   

   

• Test Case 1

  
  Input (stdin)

  2
  
  1 5
  
  6 10
  
  

  Expected Output

  6
  
  30

• Test Case 2

  
  Input (stdin)

  2
  
  5 1
  
  8 12
  
  

  Expected Output

  0
  
  30