1

我对编程相当陌生，我想尝试编写一个程序来查找一系列数字中素数的数量。当我通过编译器运行该程序时，我没有收到任何错误，但是当我尝试实际运行该程序时，它说只有 2 个，这是不正确的。我认为应该是 168 左右。如果您能帮助指出我的错误，我将不胜感激。提前致谢！ 

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

void primeFinder(void);

int main(void)
{
    printf("Prime numbers from 1 to 1000:\n\n");
    primeFinder();

    return 0;
}


void primeFinder(void)
{
    int i;
    int j;
    int k;
    int n_primes = 0;

    //i is the number to be tested:
    for ( i = 2 ; i <= 1000 ; i++ )
    {
        //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
        for ( j = 2, k = 0 ; j <= sqrt(i) ; j++ )
        {
            //i is not prime, whatever is the value of j:
            if ( i % j == 0 )
            {
                //If remainder is 0, there is no need to test that i anymore:
                break;
            }
            else
            {
                k++;
            }

        } //End of inner for
            //i is prime:
        if ( k == i - 2 )
        {
            printf("%d\t", i);
            n_primes++;
        }
    } //End of outer for
    printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);
}
4

8 回答 8

1

我给初学者程序员的一个我发现实际上很有帮助的建议是：“想想模块化！” 换句话说，训练自己分而治之；如何将问题分解为其基本组成部分？

您的程序的一个好的框架如下：

#include <stdio.h>

typedef int BOOL;

#define TRUE 1
#define FALSE 0    

BOOL is_prime(int number);

int main()
{
    printf("Prime numbers between 1 and 1000:\n");

    int i;
    for (i = 1; i <= 1000; ++i)
    {
        if (is_prime(i))
        {
            printf("%d\n", i);
        }
    }

    return 0;
}

// ...

这是因为，稍后，如果您需要确定一个数字是否为素数，您可以简单地复制并粘贴您现有的实现。

这是is_prime我经常使用的一种实现，并且做得很好：

BOOL is_prime(int number)
{
    // If the number is less than two, then it is not prime.
    if (number < 2)
    {
        return FALSE;
    }

    // If the number is two, then it is prime.
    if (number == 2)
    {
        return TRUE;
    }

    // If the number is even, then it is not prime.
    if (number % 2 == 0)
    {
        return FALSE;
    }

    // Try and divide the number by all odd numbers
    // less than or equal to its square root. If
    // we can, then it is not prime. Otherwise, it is.
    int i;
    for (i = 3; i * i <= number; i += 2)
    {
        if (number % i == 0)
        {
            return FALSE;
        }
    }
    return TRUE;
}
于 2013-10-09T19:43:37.260 回答
0

似乎您在中间更改了算法，即i-1您测试了直到 ，而不是检查除数（这是浪费的）sqrt(i)。

问题是您只更改了循环条件，但没有更新以下条件：

if ( k == i - 2 )

您有 2 个选项：

  1. 回滚到朴素算法并将循环条件更改为：

    for( j = 2, k = 0 ; j <= i-1 ; j++ )

  2. 改变你的程序逻辑，这样你只需要知道除数之外的除数是否1 存在，而不管这些除数的数量。

于 2013-10-09T19:46:59.090 回答
0

如果一个数是素数，k将递增到 的值sqrt(i)。如您所见，if 条件并不总是为真。

而不是使用计数器，您只需要一个标志来知道它是否是素数。也许是这样的：

    //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
    for ( j = 2, k = 1 ; j <= sqrt(i) ; j++ )
    {
        //i is not prime, whatever is the value of j:
        if ( i % j == 0 )
        {
            //If remainder is 0, there is no need to test that i anymore:
            k = 0;
            break;
        }
    } //End of inner for
    if (k) // i is prime
    {
    ...
于 2013-10-09T19:47:24.413 回答
0

if ( k == i - 2 )sqrt(i) - 2这个检查是错误的，前一个块只针对数字循环。你需要检查sqrt(i) -2

于 2013-10-09T19:38:39.307 回答
0

j达到 的平方根后退出内循环i。因此k不计算不除数的全数i。

于 2013-10-09T19:39:10.660 回答
0

为什么要麻烦跟踪k？只需设置一个标志来告诉您该数字是否为素数：

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

int num_primes(int limit) {
    int i;
    int j;
    int n_primes = 0;
    bool is_prime; /* note stdbool.h in the includes */

    for (i = 2; i <= limit; i++) {
        is_prime = true;
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        /* This could be written as `if (is_prime) n_primes++;` */
        n_primes += is_prime;
    }
    return n_primes;
}
于 2013-10-09T19:44:32.260 回答
0

这是你的支票。你这样做的方式有点奇怪。我认为更简单的方法是创建一个标志并将其设置为 true。所以你假设这个数字是素数。在您进行操作时，如果您发现该数字不是质数，请将标志设置为 false。之后，检查标志是否仍然为真，如果是则打印结果。这就是我所说的：

  int i;
int j;
int k;
int n_primes = 0;
bool flag;

//i is the number to be tested:
for ( i = 2 ; i <= 1000 ; i++ )
{
    //Assume it's prime
    flag=true;
    //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
    for ( j = 2 ; j <= sqrt((double)i) ; j++ )
    {
        //i is not prime, whatever is the value of j:
        if ( i % j == 0 )
        {
            //If remainder is 0, there is no need to test that i anymore:
            flag=false;
            break;
        }
    } //End of inner for
        //i is prime:
    if ( flag==true )
    {
        printf("%d\t", i);
        n_primes++;
    }
} //End of outer for
printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);
于 2013-10-09T19:45:32.267 回答
0

问题在排队

if ( k == i - 2 )

i 的值是固定的，k 是可变的。所以下面的行只对 i=2 和 3 执行。所以你得到答案 2。

if ( k == i - 2 )
{
      printf("%d\t", i);
      n_primes++;
}

您可能会发现以下代码很有用：

#include<stdio.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
int isPrimeNumber(int num)
{
    int i=2;
    int len=sqrt(num);
    if(num<2) return FALSE;
    while(i<=len)
    {
        if(num%i==0)
        {
            return FALSE;
        }
        i++;
    }

    return TRUE;
}

int countPrimeNumbersInRange(int start, int end)
{
    int count=0;
    while(start<=end)
    {
        if(isPrimeNumber(start))
        {
            printf("%d\t",start);
            count++;
        }
        start++;
    }
    return count;
}

int main()
{
    printf("\n\nIt was found %d prime(s) in the inverval considered.\n", countPrimeNumbersInRange(1, 1000));
    return 0;
}
于 2017-05-30T07:08:10.770 回答