"Magic Fraction" finder

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) != 1

And 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:

1. Input: 1
Output: 0

Explanation: There is no fraction < 1 whose numerator * denominator = 1!

2. Input: 3
Output: 3

Here 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;
}


• Optimize this code and reduce its time complexity. The words, "Can you please help to optimize..." go a long way. Of course if you're paying, that's different. Aug 23, 2014 at 6:13

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.

In accordance with the rules of code review I'll ignore your request and just concentrate on the review of the code.

1. The task says that the problem is to find fractions a/b with a * b = N! as one of the requirements. Further down it also states that the input N will be given and that it can be in the range [1, 500]. The first thing you do is to compute the factorial of the input. You should be aware that factorial grows very quickly and 500! is in the order of 10^1134 which is way beyond any native data type in C. As you compute the factorial in int your code will fail for any input larger than 12 but even unsigned long long (64bit) won't get you much further than 20 for the input. This means you will have to find a different approach to solve this problem.

2. You should take care to properly format your code. Any IDE will do that pretty much automatically for you these days so there is no excuse for poorly formatted code. Well formatted code is easier to read, understand and therefor maintain.

3. Don't use single letter variables - variables should be named in accordance to what their value represents. Even if you think it's not necessary for a little one off program like this you should still practice it - Train like you fight because you will fight like you train.