C 中的素数生成器

Question

这是Link的问题：http://www.spoj.com/problems/PRIME1/

基本上我们有两个极限，我们必须打印出它们之间的所有素数...

这是我的代码（语言 == C）：

#include <stdio.h>

void IsPrime(int test){
    for(int i= 2; i<test; i++){
        if(test%i==0){
            return;
        }
    }
    printf("%d\n",test);
}

int main(){
    int T,lower,upper;
    scanf("%d",&T);

    while(T--){
        scanf("%d",&lower);
        scanf("%d",&upper);

        for(int i = lower;i<=upper;i++){
            if(i>1){
            IsPrime(i);
            }
        }  
    }
return 0;
}

在我的本地机器上我运行这适用于简单的测试用例...我从网站上收到的消息是超时错误所以我想知道是否有更有效的方法来解决这个问题因为显然我解决得不够快？

Answer 1

您可以尝试以下方法，它对测试数量进行了轻微优化，并跳过任何大于 2 的偶数：

int isprime (int v)
{
    int i;

    if (v < 0) v = -v;                          /* insure v non-negative */
    if (v < 2 || !((unsigned)v & 1))    /* 0, 1 + even > 2 are not prime */
        return 0;

    if (v == 2) return 1;

    for (i = 3; i * i <= v; i+=2)
        if (v % i == 0)
            return 0;

    return 1;
}

如果可以使用数学库和math.h，下面的可能会更快：

int isprime (int v)
{
    int i;

    if (v < 0) v = -v;                          /* insure v non-negative */
    if (v < 2 || !((unsigned)v & 1))    /* 0, 1 + even > 2 are not prime */
        return 0;

    if (v == 2) return 1;

    for (i = 3; i <= sqrt (v); i+=2)
        if (v % i == 0)
            return 0;

    return 1;
}

我对两个版本的计时都在 int 范围内，值在 1-2 百万之间，它们很接近。

注意：在重复调用的实际测试中，带有i * i <= v的版本（下面的isprime2）始终比带有[=19的调用快=]（下面的 isprime3）。例如：

$ ./bin/isprimetst2
  isprime  (1.650138 sec) - 78497 primes
  isprime2 (0.805816 sec) - 78497 primes
  isprime3 (0.983928 sec) - 78497 primes

短驱动程序迭代了 0-2000000 中的所有素数，例如：

r = 0;
t1 = clock ();
for (v = 0; v < 2000000 - 1; v++) r += isprime2 (v);
t2 = clock ();
printf (" isprime2 (%lf sec) - %u primes\n", (t2-t1)/CLOCKS_PER_SEC, r);

r = 0;
t1 = clock ();
for (v = 0; v < 2000000 - 1; v++) r += isprime3 (v);
t2 = clock ();
printf (" isprime3 (%lf sec) - %u primes\n", (t2-t1)/CLOCKS_PER_SEC, r);

Answer 2

首先，您不必检查直到 n 的每个数字来确定 n 是否为素数，只需检查其平方根（有数学证明，现在不打算给出）。所以：

void IsPrime(int test){
    // i <= sqrt(test)
    // but to avoid sqrt you can do i * i <= test
    for(int i= 2; i * i <= test; i++){
        if(test%i==0){
            return;
        }
    }
    printf("%d\n",test);
}

接下来，我们知道在2之后，其他的素数都是奇数，所以如果把2当作特例，我们可以循环2：

// Do greater than one check only once
if (lower > 1) {
    // Special case - lower is 2
    if (lower == 2) {
        printf("%d\n", 2);
        ++lower;
    }

    for(int i = lower; i <= upper; i += 2){
        IsPrime(i);
    }
}

但是，由于您必须执行 T 次，因此您最终会进行比需要更多的检查。此外，这个问题对 n 和 m 有限制，所以它对于筛子来说基本上是完美的，正如@HennoBrandsma 所说。

使用这些优化，你应该去找到所有素数的极限，并将它们存储在一个容器中。然后，当提示范围时，只需遍历筛子并打印出数字。

（这将需要您稍微更改 IsPrime 函数 - 不要立即打印数字，让它 return true 或 false，然后基于此，将数字添加到容器）

Answer 3

您可以使用 C 中的库 maths.h 并使用 sqrt 函数计算给定数字的平方根。所以程序可能是这样的：

#include <stdio.h>
#include <maths.h>

int isPrime(int number){
    int i;
    if(number % 2 == 0){
        return;
    }

    for(i=3; i<=sqrt(number); i++){
        if(number % i == 0){
            return;
    }
    printf("%d\n",number);
}

int main(){
    int lower,upper,i;
    if(lower >1){
        if(lower == 2){
            printf("2\n");
        }

        for(i=lower; i<=upper; i++){
            isPrime(i);
        }
    return 0;
}

简而言之，您可以使用 if-else 条件使用一些额外的检查（例如 if(number % 2 == 0)）来降低 program.For 示例的时间复杂度，新的 if 条件可能是 if (number % 5 ==0) 等，因此在这些条件的帮助下，在许多情况下检查不会进入 for 循环，这将减少程序的时间。

Answer 4

#include<stdio.h>
int main()
{
    int low,high,j;
    int prime(int);
    int t;
    scanf("%d",&t);
    while (t>0)
    {
        scanf("%d %d",&low,&high);
        while (low<=1)
        {
            low++;
            continue;
        }
        for (j=low;j<=high;j++)
        {
            if (prime(j)){
                printf("%d\n",j);
            }
        }
        printf("\n");
        t--;
    }
    return 0;
}

int prime(int n)
{
    int i;
    for (i=2;i*i<=n;i++)
    {
        if (n%i==0){
            return 0;
        }
    }
    return 1;
}

C 中的素数生成器

Prime Number Generator in C

c

math

primes