主页 / coding / 问题 / 78930917
Accepted
nkminion
Asked: 2024-08-30 15:39:22 +0800 CST

编写了一个程序来打印素数，我该如何使它更好？[重复]

  • 772

我前一天开始学习 C，并编写了一个程序来在给定的范围内打印。范围的最小值和最大值由用户给出。

#include <stdio.h>
int check(int number)
{
    if (number == 1)
    {
        return 0;
    }
    int count = 2;
    while (count < number)
    {
        if (number%count == 0)
        {
            return 0;
        }
        count++;
    }
    return 1;
}
void main()
{
    int i,min,max;
    printf("Enter start of range: ");
    scanf("%d",&min);
    printf("Enter end of range: ");
    scanf("%d",&max);
    for (i = min;i < max;i++)
    {
        if (check(i) == 1)
        {
            printf("%d\n",i);
        }
    }
}

我得到了预期的输出，但我想知道是否有更好的方法在输入的数字为 1 时返回 0，或者在我看来它不像胶带代码。

我在程序进行 while 循环检查数字是否大于 1 之前插入了此代码块。

if (number == 1)
    {
        return 0;
    }

我获得了预期的输出，但我想知道是否有比仅放置 if 语句更好的方法。

我的问题与建议的问题不同，因为我想知道是否有更好的方法来确定 1 是否不是质数。建议的问题是使用 if 语句，就像我做的那样。

c

8 个回答

  1. 如果你想成为 ac 程序员，这更有用...如果我输入“frog”作为最小值会发生什么。现在你进入了错误检测和恢复的世界

    • 4

  2. 这是所有初级程序员都要面对的问题之一：如何检查一个数字是否为质数，一般思路如下：

    • 制作一个计数器，从 2 开始，一直到数字本身，然后使用模数函数进行检查。
      （问题是，你真的必须走那么远吗？想象一下你正在检查 37，你的计数器真的需要上升到 36 吗？）
    • 制作一个计数器，从 2 开始，一直到数字本身的一半，然后使用模数函数进行检查。
      （再次提出同样的问题，你真的必须走那么远吗？想象一下，你正在检查 391，当你有 17 和 23 时，你已经拥有了它们全部。因此不需要超过 ...（不是数字的一半，而是 ...）。）
    • 哦，你是对的：制作一个计数器，从 2 开始，一直到数字本身的平方根，然后使用模函数进行检查。
    • 3
  3. Best Answer

    对于有效输入，您的程序可以按预期运行，这是一个好的开始。以下是改进代码的方法，尤其是改进check所要求的功能：

    • main使用不带参数的正确原型： int main(void)。
    • 检查有效输入：scanf()返回1输入的整数，否则必须明确处理错误。
    • 对函数使用更具解释性的名称，check例如isprime。
    • 在 C 中，布尔函数返回0false 而返回非零值是惯用语，表示 true。只是测试if (isprime(i))更易读。
    • 检查是否有更多值要拒绝：if (n < 2)而不是if (n == 1)。如果您不能假设参数n至少为2，则需要使用类似这样的测试来拒绝较低的值。使用不同的循环，您可以尝试避免此测试，但不值得付出努力：此测试简单易读，如果大多数值有效，则几乎不会花费任何成本。
    • 一旦商小于除数，就应该停止对除法余数的测试。
    • 在循环之前明确测试 2 并且仅在循环中测试奇数除数将进一步提高性能。
    • 要计算某个范围内的素数，试除法的效率低于古老的埃拉托斯特尼筛法。

    以下是修改后的版本：

    #include <stdio.h>

    int isprime(int number)
    {
    if (number < 2) {
    return 0;
    }
    if (number % 2 == 0) {
    return number == 2;
    }
    for (int divisor = 3;; divisor += 2) {
    // optimizing compilers will likely compute both the
    // quotient and remainder with a single instruction
    int quotient = number / divisor;
    int remainder = number % divisor;
    if (quotient < divisor)
    return 1;
    if (remainder == 0)
    return 0;
    }
    }

    int main(void)
    {
    int i, min, max;

    printf("Enter start of range: ");
    if (scanf("%d", &min) != 1) {
    printf("invalid input\n");
    return 1;
    }
    printf("Enter end of range: ");
    if (scanf("%d", &max) != 1) {
    printf("invalid input\n");
    return 1;
    }
    for (int i = min; i < max; i++) {
    if (isprime(i)) {
    printf("%d\n", i);
    }
    }
    return 0;
    }

    • 2

  4. 除了检查范围内的每个数字是否为素数之外，还有其他方法可供考虑：

    埃拉托斯特尼筛法

    是一种生成1到N之间所有素数的算法。

    它的时间复杂度O(max log log max)使其速度更快。但是，它对大数字有缺点，例如高空间要求和缓存抖动。有针对这些问题的算法变体，如分段筛法和增量筛法。

    预先计算的数组

    对于 32 位整数，有 105'097'565 个正素数。您可以编写程序来生成它们，也可以在互联网上找到包含它们的存档文件并使用它。然后将它们放入您的程序中（例如，放入您的程序读取的文件中）。

    您可以将它们存储为有序的整数数组，然后O(log n)使用二进制搜索找到范围内第一个素数的位置（它实际上是 O(1)，因为 n 是一个常数 105'097'565）。然后您只需遍历并打印数组，直到得到一个大于您的数字max。

    难度考虑

    如果您刚刚开始学习 C 语言，那么这些选项在现阶段对您来说可能太多了。

    然而，即使你对所读内容的一半都不理解，了解它们也是件好事。然后，在你学习和练习更多之后，你可以重新回顾它们并尝试实现它们。并为你的进步感到自豪 😁

    • 1

  5. [ 有点晚了才参加 Prime 派对]

    我怎样才能让它变得更好？

    修复主要检查

    check(0)报告属实。 check(any_negative)报告属实。两者都应报告为假。

    太慢了

    check(n)迭代次数最多为n次。一个简单的改变最多迭代sqrt(n)次数。对于较大的 来说，这要快 10,000 倍n。

    当除数小于或等于商时进行迭代。

    int prime_check(int number) {
  if (number % 2 == 0) {
    return number == 2;
  }
  // Do not use divisor*divisor <= number as that overflows for a large prime.
  // Good compilers emit efficient code for number / divisor and
  // nearby number % divisor, doing both for the time cost of one.
  for (int divisor = 3; divisor <= number / divisor; divisor += 2) {
    if (number % divisor == 0) {
      return 0;
    }
  }
  return number > 1;
}

    有疑问的最大值

    我希望max成为测试范围的一部分。

      printf("Enter end of range: ");
  scanf("%d",&max);
  // for (i = min; i < max; i++)
  for (i = min; i <= max; i++)

    然而，当 时，这是一个问题max == INT_MAX。

    • 1

  6. 有几种方法可以改进素数检测算法本身。之前已经有人详细回答过这个问题，例如这里，所以我就不再赘述了。

    接下来的问题是如何验证输入。scanf()返回成功转换的值的数量，因此必须检查以确保用户输入了有效的整数。此外，还应检查值是否在允许的范围内。该check()函数假定参数是正整数，因此必须使其对非正整数具有鲁棒性，或者必须确保仅使用正整数调用它。

    具体来说，支票可以改为：

        if (number <= 1)
    {
        return 0;
    }

    但是，如果输入似乎有误，最好通知用户。总之，该main()函数可以编写如下：

    int main()
{
    int i,min,max;
    printf("Enter start of range: ");
    if(scanf("%d",&min) != 1)
    {
       printf("Input must be an integer\n");
       return 0;
    }
    if(min < 1)
    {
       printf("Input must be a positive integer\n");
       return 0;
    }
    printf("Enter end of range: ");
    if(scanf("%d",&max) != 1)
    {
       printf("Input must be an integer\n");
       return 0;
    }
    if(max < min)
    {
       printf("Range is empty\n");
       return 0;
    }
    for (i = min;i <= max;i++)
    {
        if (check(i) == 1)
        {
            printf("%d\n",i);
        }
    }
}

    注意：在for-loop中，我将结束条件更改为，i <= max因为用户可能希望范围的结束包含在检查的值中。

    正如这个例子所示，编写一个在一切顺利时能正常工作的程序通常很容易。但编写一个对所有异常都具有相当强健性的程序则要困难得多。

    • 0

  7. 几年前，我从一本书中得到了这个，可能是“C语言算法”，它使用sqrt()和floor()来查看何时中断循环，并添加了一些我自己的小补充：

    /* return 1 if n is a prime number  */
int is_prime(unsigned int n) {
    unsigned int spia,f;
    if ( !n ) return 0;
    if ( n <= 3 ) return 1;
    if ( (n % 2) && (n % 3) ) {
      spia = (unsigned int) floor(sqrt(n));
      for ( f=5 ; (n % f) && (n % (f+2)) && f <= spia ; f+=6 ) ;
      if ( f > spia ) return 1;
    } // endif
    return 0;
}

    根据以前的答案，我检查了这个版本，其中 sqrt() 被删除并替换为 / （整数除法），以查看何时中断循环：

    int is_prime_w_div(unsigned int n) {
    unsigned int f;
    if ( !n ) return 0;
    if ( n <= 3 ) return 1;
    if ( (n % 2) && (n % 3) ) {
      for ( f=5 ; (n % f) && (n % (f+2)) ; f+=6 ) {
            if ( f > n/f ) break;
      } // endfor
      if ( f > n/f ) return 1;
    }
    return 0;
}

    我在运行 Raspbian Linux 的 Raspi400 和运行 OpenSuse Leap15.6 的 Geekom Mini IT13 Core i9-13900H 上对两个版本进行了超过 1000 万个整数（从 0 到 10000000）的计时，在两种情况下， sqrt() 版本都是最快的：

    /* testprime.c */
#include <stdio.h>
#include <math.h>

/* put is_prime and is_prime_w_div here */

int main(void) {
  unsigned int i,cnt;
  for ( cnt=0,i=0 ; i<10000000 ; i++) {
    if (is_prime(i)) cnt++;
    /* if (is_prime_w_div(i)) cnt++; */
  } /* endif */
  printf("found %u primes\n",cnt);
  return 0;
}

/*
 * gcc testprime.c -lm
 * time ./a.out
 */

    那么故事是怎样的呢？在现代硬件上，浮点数学是在硬件中进行的，并且 sqrt() 不会在每次迭代中循环调用。还是我遗漏了其他内容？

    • 0

  8. 我与您分享另一种实现您的目标的方法。

    首先要注意：为了避免在每次调用检查函数时都进行“1 号”检查，请将 if 控制移出该函数和 for 循环之外。这样，您将能够执行一次此检查。

    第二点：使用递归函数对您想要分析的每个数字进行迭代检查。

    检查功能变为：

    int check(int counter, int number)
{
    
    if(number%counter){
        //mod result is not zero
        //increase counter
        counter++;

        //if counter is equal to number
        //it means that number is prime - return 1 to caller!
        //otherwise call check function again with new counter value
        if(counter==number)
            return 1;
        else
            if(check(counter, number))
                //check returns 1 - number is prime! return 1 to caller
                return 1;  
            else
                //check returns 0 - number is not prime! return 0 to caller
                return 0;
    }else{
        //number is not prime
        //return 0 to caller
        return 0;
    }

}

    使用递归调用，您可以执行迭代检查而无需使用循环，从量子时间的角度来看，您可以节省资源并提高效率。

    这是我的完整代码，带有注释：

    #include <stdio.h>

//declare functions
int check(int counter, int number);

int main()
{
    int i,min,max;
    printf("Enter start of range: ");
    scanf("%d",&min);
    printf("Enter end of range: ");
    scanf("%d",&max);
    
    // if first number is 1, i'll skip it
    if(min == 1){
        min++;
    }

    if(min == 2){
        //2 is prime, print it and increment min
        printf("%d\n",min++);
       
    }

    for (i = min;i <= max;i++)
    {
   
        
        //call recursive function for checking prime
        if (check(2,i))
            printf("%d\n",i);
        

    }
    return 0;
}


/*check function is recursive.
*  it acceptes counter and number values
*  perform prime check:
*    - it's prime number - recursive function stack will be close and return 1
*    - it's not prime number - counter will be increased and check function will be called again from itself
*/  
int check(int counter, int number)
{

    if(number%counter){
        //mod result is not zero
        //increase counter
        counter++;

        //if counter is equal to number
        //it means that number is prime - return 1 to caller!
        //otherwise call check function again with new counter value
        if(counter==number)
            return 1;
        else
            if(check(counter, number))
                //check returns 1 - number is prime! return 1 to caller
                return 1;  
            else
                //check returns 0 - number is not prime! return 0 to caller
                return 0;
    }else{
        //number is not prime
        //return 0 to caller
        return 0;
    }

}

    优点：代码布局清晰，量子时间消耗更少。

    缺点：稍微复杂一点，堆栈内存使用较少。

    最后的考虑：为了获得更多改进，您应该对输入（最小值和最大值）实施控制，以避免意外行为

    编辑：我修改了我的代码，删除了指针并移动了堆栈内存的使用

    • -2

相关问题