c - SPOJ Prime Generator 的 C 代码有什么问题？

Question

我是一名初级程序员，3 个月前开始编码。我决定在 SPOJ 上做题，但我经常陷入困境。我完成了问题 1，即生命和宇宙，这很容易，但我陷入了这个问题。我写了以下代码:

#include <stdio.h>
#include <math.h>

int main () {
int m,n,i,j=2, t,counter=0;

scanf ("%d", &t);

while (t--) {

    scanf ("%d%d", &m,&n);

    for (i=m; i<=n; i++) {

        for (j=2; j<(int)sqrt(i); j++) {
            if (i%j==0) {
                break;
            }
            else {
                printf ("%d\n", i);
                break;
             }
         }
    }
  }
return 0;
}

我无法弄清楚我做错了什么以及哪里做错了。

我还尝试了一个不同的版本，它给出了正确的答案，但该代码花费了很长时间并给出了 TLE 。代码如下:

#include <stdio.h>
int main () {
int m,n,i,j=2, t,counter=0;

scanf ("%d", &t);

while (t--) {
    scanf ("%d%d", &m,&n);

    for (i=m; i<=n; i++) {
        while (j<=i) {
         if (i%j==0)
         counter++;
         j++;
        }
        if (counter==1)
        printf ("%d\n",i);
        counter=0; 
        j=2;
    }
 }
return 0;
}

我如何为 SPOJ 和其他编程竞赛做好准备？我哪里还欠缺？

Answer 1

一些可能有帮助的事情；

1. 正如其他人建议的那样，学习一些调试技巧。

2. 了解算法以及如何估计运行时复杂度。

3. 在第二个示例中，您的代码如下所示(评论是我的)。在此代码中，您尝试通过查找数字的因子来确定 i 是否是素数。如果 i 设置为 5，则 while 循环将这些值分配给 j : [2, 3, 4, 5]，然后我们执行以下操作模数运算: 5%2, 5%3, 5%4 和 5%5 。你真的不需要测试 i 是否能被它自己整除(这不是素数吗？只能被 1 和它本身整除)。您将需要稍微修改以下逻辑，但是您可以通过外循环消除每次迭代的一个模数运算。

       for (i=m; i<=n; i++)           // outer loop
       {
           while (j<=i)               // inner loop
           {
               if (i%j==0)            // does this work as intended?
                   counter++;
               j++;
           }
   

4. 考虑相同的循环，让我们看看如果 m 是 100 会发生什么(这意味着 i 将从 100 开始)。您的内部循环将计算测试数字(即 i )除以 [2,100] 范围内的每个数字的余数。第一个模运算 (100 % 2) 将返回 0，因此我们立即知道 100 是一个合数。此时，没有理由继续执行额外的测试。要解决我在第 3 点和第 4 点中提出的问题，您可以将内部循环重写为(我已将 j 的初始化移动到内部循环的顶部，并引入了一个新变量 isPrime ):

       bool     isPrime;
       for (i=m; i<=n; i++)           // outer loop
       {
           j = 2;
           isPrime = true;
           while (j < i)               // range of j is now [2, i)
           {
               if (i%j==0)             // number is a composite
               {            
                   isPrime = false;
                   break;
               }
               j++;
           }
   
           if(isPrime)            // never found a divisor
           {
                printf ("%d\n",i);
           }
       }   
   

5. 请注意，在第 3 点和第 4 点中，我所做的只是询问小输入会发生什么，并查看查找逻辑错误时会发生什么。

6. 考虑使用暴力方法以外的方法。在该问题中，您被告知 1 <= m <= n <= 1000000000, n-m<=100000 ，因此您可能需要确定大量测试用例是否是质数(即 n-m = 100,000)或正在处理非常大的测试用例(即 n = 1,000,000,000)。考虑到这些极端情况，暴力方法的计算成本可能非常高。要看到这一点，请考虑 m = 999,900,000 and n = 1,000,000,000 是一个有效范围。这意味着您可能需要考虑其他素性测试方法。

7. 不要放弃。编程是一项智力练习，进步的唯一方法就是练习、尝试、从错误中学习(而且会有很多错误)。这确实是提高编程水平的唯一方法