How to optimize this code

1

Question

#include <stdio.h>
int fact(int);
void main()
{
long int n,count=0;
scanf(“%ld”,&n);
long int a[n];
int i,j;
for(i=0;i<n;i++)
{
scanf(“%ld”,&a[i]);
}
int g;
for(j=0;j<(n-1);j++)
{
for(g=j+1;g<n;g++)
{count+=fact(a[j]*a[g]);
}
}
printf(“%ld”,count);
}
int fact(int z)
{
int i,ct=0;
for(i=1;i<=z;i++)
if(z%i==0)
ct++;
return ct;
}

2
  • First, please format your code by putting it between three backticks like so: ``` Code ```. Otherwise it’s completely unreadable.
  • You actually compute something complete different: you compute all pairwise products, compute the number of divisors for each one, and sum them up. Read the question again. The question asks for each j, to compute the product of all numbers without a[j], then count the divisors and sum the up.
  • Be careful, in the line a[j] * a[g]happens an integer overflow.
  • There are a lot faster ways to compute the number of divisors of a number, once you have a prime factorization. For learning it, check out this article.
  • But that speedup will still not be enough for solving the problem. You need some clever ideas, to make it work. Check out the editorial for the solution: KETEKI2C editorial
3 Likes
3

thanks budy it was very helpful to me…