在 C 代码 + 循环中优化 I/O（输出）

Question

我有一个代码，它从 stdin 读取大约 (10^5) int(s) ，然后在执行 ## 后将它们输出到 stdout 上。我通过使用“setvbuf”和使用“fgets_unlocked()”读取行来处理输入部分，然后解析它们以获得所需的 int(s)。我有两个无法解决的问题：

1.）当我在标准输出上打印 int(s) 500 万时，它花费了大量时间：有没有办法减少这个（我尝试使用 fwrite() 但由于使用 fread 的原因，o/p 打印了不可打印的字符读入 int 缓冲区）

2.）在解析 int(s) 的输入后，说“x”，我实际上通过在循环中对 no 执行 %(mod) 来找到除数的 no。（参见下面的代码）：也许这也是一个我的代码超时的原因：对此的任何建议都需要改进。非常感谢这实际上是来自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

//Prob 2 你现在最大的问题是......你只是想找到除数的数量吗？

我的第一个建议是在某种程度上缓存您的结果......但这可能需要您开始时拥有的存储量的两倍：/。

您可以做的是预先生成素数列表（使用筛算法）。理想的情况是知道N列表中最大的数字并生成所有素数直到其平方根。现在，对于列表中的每个数字，您希望找到他作为因子乘积的表示，即

n = a1^p1 * a1^p2 *... *an^pn

那么除数之和就是。

((a1^(p1+1) - 1)/(a1 - 1))*((a2^(p2+1) - 1)/(a2-1))*...*((an^(pn+1) - 1)/(an-1))

要了解你有（对于 n = 8） 1+ 2 + 4 + 8 = 15 = (16 - 1)/(2 - 1)

它将大大提高速度，但整数分解（你真正在做的事情）真的很昂贵......

编辑：

在您的链接中，最大值为 5000000，因此您最多有 700 个素数

简单的分解算法

void primedecomp(int number, const int* primetable, int* primecount,
      int pos,int tablelen){
    while(pos < tablelen && number % primetable[pos] !=0 )
       pos++;

    if(pos == tablelen)
      return

     while(number % primetable[pos] ==0 ){
        number = number / primetable[pos];
        primecount[pos]++;
     }
     //number has been modified
     //too lazy to write a loop, so recursive call
     primedecomp(number,primetable,primecount, pos+1,tablelen);
    
}

编辑：而不是计数，a^(n+1)使用计算primepow = a; primepow = a*primepow;

在有 hashmap 的 C++ 或 java 中，它会更干净。最后 primecount包含pi我上面讨论的价值观。

即使看起来很可怕，你也会创造primetable唯一的一次。现在这个算法在最坏的情况下运行，O(tablelen)其中O(square root(Nmax))。你的初始循环运行在O(Nmax).