1 
 #include<stdio.h>
 #include<time.h>

 int main()

  {

    clock_t start;
    double d;
    long int n,i,j;
    scanf("%ld",&n);
    n=100000;
    j=2;
    start=clock();
    printf("\n%ld",j);

       for(j=3;j<=n;j+=2)
       {
          for(i=3;i*i<=j;i+=2)

          if(j%i==0)
            break;

           if(i*i>j)
          printf("\n%ld",j);

        }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;
    printf("\n%f",d);

}

当上述程序的 n=100000 时，我得到了 0.015 秒的运行时间。我还在 C 中实现了埃拉托色尼筛算法，并在 n=100000 时获得了 0.046 的运行时间。

我的上述算法如何比我已经实现的 Sieve 算法快。

我上述程序的时间复杂度是多少？

我的筛子的实施

 #define LISTSIZE 100000    //Number of integers to sieve<br>
 #include <stdio.h>
 #include <math.h>
 #include <time.h>

int main()
{   


    clock_t start;
    double d;
    long int list[LISTSIZE],i,j;
    int listMax = (int)sqrt(LISTSIZE), primeEstimate = (int)(LISTSIZE/log(LISTSIZE));

    for(int i=0; i < LISTSIZE; i++)
        list[i] = i+2;
    start=clock();

    for(i=0; i < listMax; i++)
    {
        //If the entry has been set to 0 ('removed'), skip it
        if(list[i] > 0)
        {
            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                if((list[j] % list[i]) == 0)
                    list[j] = 0;
            }
        }
    }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;

    //Output the primes
    int primesFound = 0;
    for(int i=0; i < LISTSIZE; i++)
    {
        if(list[i] > 0)
        {
            primesFound++;

            printf("%ld\n", list[i]);
        }
    }
    printf("\n%f",d);
    return 0;
}
4

6 回答 6

3

有许多事情可能会影响您的结果。可以肯定的是，我们需要查看您的筛子实现的代码。clock另外，你电脑上的功能分辨率是多少？如果实施不允许毫秒级的高精度，那么您的结果可能在测量的误差范围内。

我怀疑问题出在这里：

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                    if((list[j] % list[i]) == 0)
                            list[j] = 0;
            }

这是删除所有素数倍数的糟糕方法。为什么不使用内置的乘法运算符来删除倍数？这个版本应该更快：

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = list[i]; j < LISTSIZE; j+=list[i])
            {
              list[j] = 0;
            }
于 2009-08-30T07:24:46.680 回答
1

我上述程序的时间复杂度是多少？

要凭经验测量程序的时间复杂度，您需要多个数据点。为多个 N 值运行您的程序，然后制作 N 与时间的关系图。您可以使用电子表格、GNUplot 或方格纸和铅笔来完成此操作。您还可以使用软件和/或简单的旧数学来找到适合您的数据的多项式曲线。

非经验性的：关于分析计算复杂性的文章很多（并在计算机科学课程中讲授过）。关于计算复杂性理论的维基百科文章可能会为进一步阅读提供一些起点。

于 2009-09-01T07:43:07.720 回答
0

您的筛子实施不正确；这就是它如此缓慢的原因：

  • 你不应该把它变成一个数字数组，而是一个标志数组（你仍然可以使用 int 作为数据类型，但 char 也可以）
  • 您不应该对数组使用索引移位，但 list[i] 应该确定 i 是否是素数（而不是 i+2 是否是素数）
  • 你应该从 i=2 开始消除
  • 通过这些修改，您应该遵循 1800 INFORMATION 的建议，并使用以 i 为步长的循环取消所有 i 的倍数，而不是 1 的步长
于 2009-08-30T08:46:56.810 回答
0

只是为了您的时间复杂度：

你有一个 ~LISTMAX 迭代的外循环和一个 max 的内循环。LISTSIZE 迭代。这意味着您的复杂性是

O(sqrt(n)*n)

其中 n = 列表大小。它实际上有点低，因为内部循环每次都会减少它的计数，并且只为每个未知数运行。但这很难计算。由于 O-Notation 提供了一个上限，因此 O(sqrt(n)*n) 应该没问题。

于 2009-09-01T08:06:42.947 回答
0

这种行为很难预测，但您应该考虑到访问内存并不便宜......对于小素数再次计算它可能会更快。

于 2009-09-01T08:14:58.967 回答
0

这些运行时间太小而没有意义。系统时钟分辨率不准确到那种水平。

要获得准确的时序信息，您应该做的是循环运行您的算法。重复数千次以使运行时间至少达到一秒，然后您可以将时间除以循环数。

于 2009-12-22T14:28:41.357 回答