A Magic Fraction for N is one that has the following properties:It is a proper fraction (the value is < 1)It cannot be reduced further (the GCD of the numerator and the denominator is 1)The product of the numerator and the denominator is factorial of N. i.e. if a/b is the fraction, then a*b = N!Examples of Magic Fractions are:1/2 [ gcd(1,2) = 1 and 1*2=2! ]2/3 [ gcd(2,3) = 1 and 2*3=3! ]3/8 [ gcd(3,8) = 1 and 3*8=4! ]2/12 for example, is not a magic fraction, as even though 2*12=4!,  gcd(2,12) != 1And Magic Fractions for number 3 are: 2/3 and 1/6 (since both of them  satisfy the above criteria, are of the form a/b where a*b = 3!)Now given a number N, you need to print the total number of magic  fractions that exist, for all numbers between 1 and N (include magic  fractions for N, too).Note:The number N will be in the range [1, 500]. (1 and 500 inclusive)  You'll have to read the input from STDIN, and print the output to  STDOUT Examples:Input: 1  Output: 0Explanation: There is no fraction < 1 whose numerator * denominator = 1!Input: 3  Output: 3Here is my code:#include <stdio.h>int fact(int no){    int res = 1;    while(no != 1){    res = res *no;    no--;    }    return res;} int gcd(int x,int y) {  int m,i;  if(x>y)      m=y;  else       m=x; for(i=m;i>=1;i--){      if(x%i==0&&y%i==0){        // printf(\nHCF of two number is : %d,i) ;         break;     }}return i;}int main(){ int n,i,j,k,cnt = 0,fa;scanf(%d,&n);for(i = 2; i <= n; i++){    fa = fact(i);    printf(%d\n,fa);    for(j = 1; j <= (fa/2); j++)    {       // printf(%d\n,j);        for(k=2; k <= fa ; k++)        {            if(j >k )            {                if(((j*k) == fa) && (gcd(j,k) == 1))                {                    cnt ++;                   // printf(inside\t j = %d k = %d\n,j,k);                }            }        }    }}cnt = cnt + (n-1);if(n >1)    printf(%d,cnt);else    printf(0);return 0;}Please help me in optimizing this code.
Magic Fraction finder
c;programming challenge;complexity;rational numbers
You have taken a very literal, brute-force approach to solving the problem.  As @ChrisWue points out, trying to compute 500! will kill you many times over.  Instead of multiplying the numbers out, try factoring instead.  Here is an outline of a solution that might work:For every \$n = 2, 3, \ldots, N\$, find the prime factorization of \$n!\$.  This is not as nasty as it sounds: if you know that the prime factorization of \$n!\$ is$$n! = \prod_i p_i^{e_i}$$then the prime factorization of \$(n + 1)!\$ is simply that and the prime factorization of \$n + 1\$.  For example,$$\begin{alignat*}{4}4! &= 2 \cdot 3 \cdot 4 &&= 2^3 \cdot 3 \\5! &= 4! \cdot 5        &&= (2^3 \cdot 3) \cdot 5            &&= 2^3 \cdot 3 \cdot 5 \\6! &= 5! \cdot 6        &&= (2^3 \cdot 3 \cdot 5)(2 \cdot 3) &&= 2^4 \cdot 3^2 \cdot 5\\\end{alignat*}$$Next, you need to partition \$n!\$ into factors \$a\$ and \$b\$.  To ensure that \$a\$ and \$b\$ have no common factors, you simply have to ensure that each prime factor \$p_i\$ is attributed to either \$a\$ or \$b\$, along with all of its exponents \$e_i\$.  For example, \$4!\$ can be partitioned as$$\begin{alignat*}{3}(a, b) &= (1&&,\ 2^3 \cdot 3) \\(a, b) &= (3&&,\ 2^3)\end{alignat*}$$but not as$$(a, b) = (2 \cdot 3,\ 2^2)$$since 2 appears in both \$a\$ and \$b\$, making \$\frac{a}{b}\$ reducible.So, the problem reduces to counting the power sets of the distinct prime factors of \$n!\$.  Half of those partitions will meet the requirement that \$a < b\$, and half will fail.