Question

can you explain this code clearly with line to line





#include
int semiprime(int n)
{
int p,f=0;
{
for (p=2;f<2&&p*p<=n;p++)
{
while(0==n%p)
n/=p,f++;
}
}
return f+(n>1)==2;
}
int main(void)
{
int i,t;
scanf("%d",&t);
while(t--)
for (i=2;i<200;i++)
if (semiprime(i)) printf("%d\n",i);
putchar('\n');
return 0;
}

Answer 1

Follow bottom-up approach in such questions. like first calculate f(0) then f(1) and so on , because there are recursive calls and functions are evaluated in post order so better start from leaf ..

f(0)=1 //obvious

f(1)=1  // obvious

f(2)= ?        i=2                                                   i=1

                   r=0+f(2/3)=0+f(0)=1                     r=1+f(1/3)=1+f(0)=1+1=2                  

f(2)=2

f(3)=?    i=3                                                i=2                                i=1

              r=0+f(3/3)=0+f(1)=0+1=1        r=1+f(2/3)=1+1=2        r=2+f(1/3)=2+1=3

f(3)=3

f(4)=?  

  i=4                                        i=3                                          

  r=0+f(4/3)=0+f(1)=1          r=1+f(3/3)=1+f(1)=2              

  i=2                                                  i=1

r=2+f(2/3)=2+f(0)=3                     r=3+f(1/3)=4

f(4)=4

f(5)=?

i=5                                               i=4                                        i=3                                 

r=0+f(5/3)=0+f(1)=1                 r=1+f(4/3)=2                       r=2+f(3/3)=2+f(1)=3    

   i=2                                   i=1

  r=3+f(2/3)=3+1=4       r=4+f(1/3)=4+f(0)=5

f(5)=5

f(6)=? 

i=6                                                  i=5                                      i=4              

r=0+f(6/3)=0+f(2)=2                    r=2+f(5/3)=3                      r=3+f(4/3)=4  

  i=3                                                     i=2                         i=1

r=4+f(3/3)=5                                      r=5+f(2/3)=6         r=6+f(1/3)=6+f(0)=7

f(6)=7