使用数组打印素数

Question

这是打印质数的代码。

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

int main()
{
    int p;   
    int i;
    int primes[50] = { 0 };
    int primeIndex = 2;
    bool isPrime;

    // hardcode prime numbers
    primes[0] = 2;
    primes[1] = 3;

    for (p = 5; p <= 100; p = p + 2) {
        isPrime = true;

        for (i = 1; isPrime && p / primes[i] >= primes[i]; ++i)
            if (p % primes[i] == 0)
                isPrime = false;

        if (isPrime == true) {
            primes[primeIndex] = p;
            ++primeIndex;
        }
    }

    for (i = 0; i < primeIndex; ++i)
         printf ("%i  ", primes[i]);

    printf("\n");
    return 0;
}

我不明白这段代码中的一些事情：

内部for循环的条件如何工作以及isPrime变量的用途是什么？

Answer 1

代码正确计算并打印所有小于或等于 100 的素数。

Why is it necessary to hard-code 2 prime numbers (2 and 3)?

2是一个特例：它是唯一的偶素数。 2 被硬编码为第一个素数，因此外循环仅测试奇数。

3 是硬编码的，因此外循环可以依赖数组内容作为其停止条件 p / primes[i] >= primes[i]。数组中需要至少有一个奇质数，以避免对数组索引进行额外的测试，例如i < primeIndex.

正如 chux 评论的那样，内部循环可以从索引 i = 0 开始，然后只需要将 2 硬编码到数组中。筛选过程的效率会稍微低一些，因为所有数字都将被不必要地测试为可被 2 整除，可以跳过，因为所有测试的数字都是奇数。

What is the use of boolean expression in the first for loop?

第一个 for 循环中的条件测试是 p <= 100。该程序枚举小于或等于 100 的素数。 primes 数组的长度为 50，足以满足此范围。如果范围大得多，则需要扩展数组大小。

布尔变量isPrime用于存储素性测试的结果。它被初始化为 true，当且仅当在内部循环中找到质因数时，它才会被重置为 false。

在内部循环之后测试变量以检查 p 是否应该附加到素数列表。

第二个 for 循环 isPrime && p / primes[i] >= primes[i] 中的条件是一个优化：它允许循环在找到除数后立即停止。该测试可以简化为 p / primes[i] >= primes[i] 并且循环将继续测试素数直到 p 的平方根。在找到除数时添加 break 语句是提前停止循环以提高效率的替代方法。

Can someone explain me how the inner for loop works?

内部循环对质数除数进行迭代，直到发现一个余数为 0 (p % primes[i] == 0) 或直到除数大于 p 的平方根 (p / primes[i] >= primes[i] ).

注意数组primes不需要初始化。

这是一个简化版本：

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

int main() {
    int primes[50];
    int i, p, primeIndex;

    // hardcode 2 prime numbers
    primes[0] = 2;
    primes[1] = 3;
    primeIndex = 2;

    // enumerate odd numbers from 5 to 100
    for (p = 5; p <= 100; p = p + 2) {
        // use a boolean variable that will be set to false if p is composite
        bool isPrime = true;

        // test all odd prime divisors up to the square root of p
        for (i = 1; p / primes[i] >= primes[i]; ++i) {
            if (p % primes[i] == 0) {
                isPrime = false;
                break;
            }
        }
        // if p is prime, add it to the array.
        if (isPrime) {
            primes[primeIndex++] = p;
        }
    }

    for (i = 0; i < primeIndex; ++i)
         printf("%i  ", primes[i]);

    printf("\n");
    return 0;
}

这是一个使用函数的更简单的版本：

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

// test if an odd number greater than 3 is a prime
bool isOddPrime(int p, const int *primes) {
    for (int i = 1; p / primes[i] >= primes[i]; ++i) {
        if (p % primes[i] == 0)
            return false;
    }
    return true;
}

int main() {
    int primes[50] = { 2, 3 };  // hardcode 2 prime numbers
    int primeIndex = 2;

    for (int p = 5; p <= 100; p = p + 2) {
        if (isOddPrime(p))
            primes[primeIndex++] = p;
    }

    for (i = 0; i < primeIndex; ++i)
         printf("%i  ", primes[i]);

    printf("\n");
    return 0;
}

使用数组打印素数

Printing prime numbers using arrays

c

arrays

boolean