-1

我必须遵循 Eratosthenes 算法的筛子，即：

初始化数组 is_prime 以便所有元素的值都为真。然后，将 is_prime[1] 的值设置为假（因为 1 不是素数。）对于 I=2 直到 sqrt(N) 将 I 的所有倍数设置为假，从 I*I 开始直到 N。最后，打印is_prime 的所有保持值为真的索引。

问题是它编译，但它不打印任何东西。您不提供输入，它应该显示 1-300 之间的所有素数。

这是我到目前为止开发的代码：

#include <stdio.h>        //Library functions
#include <math.h>
#include "simpio.h"

#define N 300             //defining constant

void displayPrime(bool checkPrime);         //Function prototypes
bool checkPrime (int I);
bool is_prime[N+1];          //Array decleration

main()                    
{        
         displayPrime(is_prime);

         getchar();      
}

void displayPrime (bool check)          //Function definitions
{
         int I;

         for(I=1; I<N; I++)
         {
                  checkPrime(I);
                  if(is_prime[I]==false)
                  {
                          printf("");
                  }
                  else if(is_prime[I]==true)
                  {
                          printf("%d\n", I);
                  }
         }
}

bool checkPrime (void)
{
         int number1, x;
         double number;

         is_prime[1]=false;

         number=sqrt(N);
         for(number1=2; number1<=number; number1++)
         {
                  for(x=number1; x<=N; x=x+number1)
                  {
                         is_prime[x]=false;
                         return(is_prime[x]);    
                  }        
                  is_prime[number1]=true;                  
                  return(is_prime[number1]);
         }                      
}

谢谢 :D

4

1 回答 1

2

你说程序不打印任何东西？在我看来，这将是一个无限循环。

考虑完成所有工作的循环：

     number=sqrt(N);
     for(number1=2; number1<=number; number1++)
     {
          // This looks like an infinite loop!
          for(I=number1; I<=N/I; I=I*number1)
          {
              I=false;    
          }        
          if(I==false)
          {
              is_prime[I]=false;  
          }
          else
          {
              is_prime[I]=true;
          }                  
          return(is_prime[I]);
     }

该内部循环无法终止。假设您使用 I=2 调用该函数。第一次进入该循环，I设置为false（0）。然后再次检查条件 ( I<=N/I) ...等等，这不是给你一个除以 0 的错误吗？

您程序中的逻辑有点混乱。您应该将程序分成两部分：计算素数，然后显示素数。在结构上，它应该如下所示：

bool is_prime[N+1]

main()
{
    // fill is_prime with true

    // and then compute the primes
    computePrimes()

    // now output primes
    for (int i = 1; i <= N; i++)
    {
        if (is_prime[i])
            printf(....);
    }
}

有了这个，你必须编写computePrimes方法。您对外循环有基本的想法，但内循环的逻辑是不正确的。考虑一下如果你的循环看起来像这样会发生什么：

for (int number1 = 2; number1 <= sqrt(N); number1++)
{
    for (int x = number1*2; x <= N; x = x + number1)
    {
        is_prime[x] = false;
    }
}

有一个优化机会，我故意没有包括在内，您可以稍后添加。它不会影响结果，只是速度。

于 2013-07-18T14:06:22.430 回答