获取所有质数

Question

我正在尝试得到从1到10的所有质数。但是我的代码不工作，有人能告诉我为什么吗？

#include<stdio.h>

int main(void) {

    int i = 10;
    int n = 10;

    for(; i > 1; i-- ) {
        while(n > 1) {
            if((i % (n - 1)) == 0) {
                printf("%d is not a prime number", i);
                break;
                n--;
            }
        }
        n = 10;
        printf("%d is a prime number", i);
    }
    return 0;
}

得到一个非常大的计算时间和没有输出。

Answer 1

我们初学者应该互相帮助。

这是一个演示程序，我尽量使用您的方法。

#include <stdio.h>

int main(void) 
{
    const int N = 10;

    for ( int i = N; i > 1; i-- ) 
    {
        int n = i - 1;
        while ( n > 1 && i % n != 0 ) n--; 

        if ( n == 1 )
        {
            printf("%d is a prime number\n", i);
        }
        else
        {
            printf("%d is not a prime number\n", i);
        }
    }

    return 0;
}

程序输出为

10 is not a prime number
9 is not a prime number
8 is not a prime number
7 is a prime number
6 is not a prime number
5 is a prime number
4 is not a prime number
3 is a prime number
2 is a prime number

用任意正值设置常量N，可以得到包括N之前的所有质数。

至于您的程序，那么您应该将第一个带有printf的语句放在内部循环之外。此外，此语句n--;必须跟在if语句之后。当i等于2时，n也等于2时，你会得到2不是质数，因为这个表达式i % (n - 1)) == 0产生true。

您可以编写一个单独的函数来检查给定的数字是否为质数。给你。

#include <stdio.h>

int is_prime( unsigned int n )
{
    int prime = ( n == 2 ) || ( n != 1 && n % 2 );

    for ( unsigned i = 3; prime && i <= n / i; i += 2 )
    {
        prime = n % i;
    }

    return prime;
}

int main( void ) 
{
    while ( 1 )
    {
        unsigned int n;

        printf( "Enter a non-negative number (0 - exit): " );

        if ( scanf( "%u", &n ) != 1 || n == 0 ) break;

        printf( "\nPrime numbers up to %u:", n );

        for ( unsigned int i = 0; i < n; i++ )
        {
            if ( is_prime( i + 1 ) ) printf( " %u", i + 1 );
        }

        printf( "\n\n" );
    }

    return 0;
}

Answer 2

As @Zaid pointed out，则由于n--位于if语句内而导致无限循环。if条件最终将失败，因此它最终将陷入无限循环。

事实证明，内部的while循环是另一个for循环。

for( n = 10; n > 1; n-- )

这就是为什么使用for循环的原因，它清楚地说明了初始化、终止条件和递增。

这不会使代码工作，但它不是无限的。

你基本上要做的是，对于每个数字，试着除以比它本身小的每个数字。

for( i = 10; i > 1; i-- ) {  // every number from 10 to 2
    for( n = i-1; n > 1; n-- ) { // every number lower than i to 2.
        if( i % n == 0 ) {
            printf("%d is not a prime number\n", i);
            break;
        }
    }

    // If n reached 1, it made it through the sieve.
    if( n <= 1 ) {
        printf("%d is a prime number\n", i);
    }
}

请注意，通过从i- 1开始n，不需要记住将i与n-1进行比较，这简化了代码，并且减少了一个潜在的bug。

有几种方法可以优化这一点。我们可以观察到以下几点：

当n>i/2时，整数永远不会被整除。因此，10永远不会被9、8、7或6整除。这意味着我们可以从i/2开始计算n，并节省大量检查。由于这是整数除法，i/2总是会向下舍入，不需要我们自己去做。

素数因子越小，它成为因子的可能性就越大。一半的数字可以被2整除，1/3可以被3整除，1/5可以被5...所以从底部开始递增n会更快。

#include<stdio.h>

int main(void) {
    int num;
    int divisor;

    // From 10 to 2.
    for( num = 10; num > 1; num-- ) {
        // From 2 to num/2, no need to go further.
        for( divisor = 2; divisor <= num/2; divisor++ ) {
            if( num % divisor == 0 ) {
                printf("%d is not a prime number\n", num);
                break;
            }
        }

        // If we got past num/2 it's prime
        if( divisor > num/2 ) {
            printf("%d is a prime number\n", num);
        }
    }

    return 0;
}

我们可以更进一步，观察到偶数永远不是质数。这意味着偶数也永远不是素因子。如果我们从奇数开始n，我们可以通过将检查次数再减半来进行计数。如果我们完全跳过偶数，这很容易。

#include<stdio.h>

int main(void) {
    int num;
    int divisor;

    // Count down from 11 by 2s.
    for( num = 11; num > 1; num -= 2 ) {
        // From 3 to num/2. No need to check 2, we skipped even numbers.
        for( divisor = 3; divisor <= num/2; divisor += 2 ) {
            if( num % divisor == 0 ) {
                printf("%d is not a prime number\n", num);
                break;
            }
        }

        // Same end condition as before.
        if( divisor > num/2 ) {
            printf("%d is a prime number\n", num);
        }
    }

    // Special case for 2.
    printf("2 is a prime number\n");

    return 0;
}

如果你想要所有的数字，你可以在主循环中放一个特殊的例子来检查它是否为偶数。同样，2是特殊大小写的，所以我们不必在循环中不断检查num != 2。

#include<stdio.h>

int main(void) {
    int num;
    int divisor;

    // Count down from 10 to 3, 2 is special cased.
    for( num = 10; num > 2; num-- ) {
        // Special case for even numbers so we can still do the
        // for loop by 2s.
        if( num % 2 == 0 ) {
            printf("%d is not a prime number\n", num);
            continue;
        }

        // 3 to num/2, odd numbers only.
        for( divisor = 3; divisor <= num/2; divisor += 2 ) {
            if( num % divisor == 0 ) {
                printf("%d is not a prime number\n", num);
                break;
            }
        }

        if( divisor > num/2 ) {
            printf("%d is a prime number\n", num);
        }
    }

    // Again, special case for 2 to reduce code operations inside the loop
    printf("2 is a prime number\n");

    return 0;
}

Answer 3

您的while循环进入无限循环，因为您正在递减if语句块中的n。

在while循环中，将n--放在if块的右大括号之后