Optimizing I/O(Output) in C code + a loop

Question

I have a code which reads around (10^5) int(s) from stdin and then after performing ## i output them on stdout. I have taken care of the INPUT part by using "setvbuf" & reading lines using "fgets_unlocked()" and then parsing them to get the required int(s). I have 2 issues which i am not able to come over with:

1.) As i am printing int(s) 5 million on stdout its taking lot of time : IS THERE ANY WAY TO REDUCE THIS( i tried using fwrite() but the o/p prints unprintable characters due to the reason using fread to read into int buffer)

2.) After parsing the input for the int(s) say 'x' i actually find the no of divisors by doing %(mod) for the no in a loop.(See in the code below): Maybe this is also a reason for my code being times out: Any suggestions on this to improved. Many thanks This is actually a problem from http://www.codechef.com/problems/PD13

# include <stdio.h>
# define SIZE 32*1024
char buf[SIZE];

main(void)
{
int i=0,chk =0;
unsigned int j =0 ,div =0;
int a =0,num =0;
char ch;

setvbuf(stdin,(char*)NULL,_IOFBF,0);

scanf("%d",&chk);
while(getchar_unlocked() != '\n');
while((a = fread_unlocked(buf,1,SIZE,stdin)) >0)
{
    for(i=0;i<a;i++)
    {
        if(buf[i] != '\n')
        {
            num = (buf[i] - '0')+(10*num);
        }
        else
        if(buf[i] == '\n')
        {   
            div = 1;
            for(j=2;j<=(num/2);j++)
            {
                if((num%j) == 0)    // Prob 2
                {
                    div +=j;
                }
            }
            num = 0;
            printf("%d\n",div); // problem 1
        }       
    }
}
return 0;
 }

Answer 1

You can print far faster than printf.

Look into itoa(), or write your own simple function that converts integers to ascii very quickly.

Here's a quick-n-dirty version of itoa that should work fast for your purposes:

char* custom_itoa(int i)
{
    static char output[24];  // 64-bit MAX_INT is 20 digits
    char* p = &output[23];

    for(*p--=0;i/=10;*p--=i%10+0x30);
    return ++p;    
}

note that this function has some serious built in limits, including:

• it doesn't handle negative numbers
• it doesn't currently handle numbers greater than 23-characters in decimal form.
• it is inherently thread-dangerous. Do not attempt in a multi-threaded environment.
• the return value will be corrupted as soon as the function is called again.

I wrote this purely for speed, not for safety or convenience.

Answer 2

Version 2 based on suggestion by @UmNyobe and @wildplasser(see above comments) The code execution took 0.12 seconds and 3.2 MB of memory on the online judge. I myself checked with 2*10^5 int(input) in the range from 1 to 5*10^5 and the execution took:

real 0m0.443s

user 0m0.408s

sys 0m0.024s

**Please see if some more optimization can be done.

enter code here
/** Solution for the sum of the proper divisor problem from codechef **/
/** @ author dZONE **/
# include <stdio.h>
# include <math.h>
# include <stdlib.h>
# include <error.h>
# define SIZE 200000

inline int readnum(void);
void count(int num);

int pft[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709};

unsigned long long int sum[SIZE];

int k = 0;

inline int readnum(void)
{
int num = 0;
char ch;
while((ch = getchar_unlocked()) != '\n')
{
    if(ch >=48 && ch <=57)
    {
        num = ch -'0' + 10*num;
    }
}
if(num ==0)
{
    return -1;
}
return num;
    }

    void count(int num)
    {
    unsigned int i = 0;
    unsigned long long tmp =0,pfac =1;
    int flag = 0;
    tmp = num;
    sum[k] = 1;
    for(i=0;i<127;i++)
    {   
    if((tmp % pft[i]) == 0)
    {
        flag =1;                // For Prime numbers not in pft table
        pfac =1;
        while(tmp % pft[i] == 0)
        {
            tmp =tmp /pft[i];
            pfac *= pft[i];
        }
        pfac *= pft[i];
        sum[k] *= (pfac-1)/(pft[i]-1);  
    }
}
if(flag ==0)
{
    sum[k] = 1;
    ++k;
    return;
}
if(tmp != 1)                        // For numbers with some prime factors in the pft table+some prime > 705
{
    sum[k] *=((tmp*tmp) -1)/(tmp -1);
}
sum[k] -=num;
++k;
return;
    }

    int main(void)
    {
    int i=0,terms =0,num = 0;

    setvbuf(stdin,(char*)NULL,_IOFBF,0);
    scanf("%d",&terms);
    while(getchar_unlocked() != '\n');
    while(terms--)
    {
    num = readnum();
    if(num ==1)
    {
        continue;   
    }
    if(num == -1)
    {
        perror("\n ERROR\n");
        return 0;
    }

    count(num);
        }
       i =0;
       while(i<k)
       {
    printf("%lld\n",sum[i]);
    ++i;
        }   
        return 0;
         }