打印用户接收范围内的 Germain 素数的 C 程序

Question

对于整数 X和 Y从用户收到(假设 X < Y)，编写程序将 X 范围内的所有 Germain 素数相加。至 Y到一个数组并在屏幕上打印这个数组中的元素。热尔曼素数是这样的素数，使得数 2p + 1 也是素数。此问题不会使用额外的字符串。否则，它将被评估为 0。
样本:

Enter X and Y: 2 15
Germain Prime Numbers in the Range: 2-3-5-11

我有一个这样的问题。我写了一个程序，但它也打印了一些错误的数字。但是，它现在不打印任何内容
这是我的代码:

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

int main() {
    int x, y, i, j, k, counter = 0, counter2 = 0;

    printf("Please enter x and y values:\n\a");
    scanf("%d %d", &x, &y);

    for (i = x; i <= y; i++) {
        for (j = 1; j <= i; j++) {
            if (i % j == 0) {
                counter++;
            }
        }                        
        if (counter == 2) {                                               
            for (k = 1; k <= 2 * i + 1; k++) {
                if ((2 * i + 1) % k == 0) {
                    counter2++;
                } 
                if (counter2 == 2) {
                    printf("%d is a germain prime number", i);
                }
            }
        }
        counter = 0;
    }
    return 0;   
}

有人能告诉我我的错误在哪里吗？
编辑:我不应该使用用户创建的函数

Answer 1

你的代码太复杂了。应该简化主循环。此外，输出不是示例显示的内容。
以下是问题:

循环 for (j = 1; j <= i; j++)是对 isPrime() 的非常低效的内联重新实现.

测试 if (2 * i + 1 % k == 0)在第二个循环中应该使用括号:if ((2 * i + 1) % k == 0)

counter2永远不会重置为 0 .设置两个 counter 会更安全和 counter2至 0在它们各自的循环之前。

实际上，调用 isPrime() 会好得多.

这是一个修改后的版本:

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

bool isPrime(int n) {
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main() {
    int x, y, i, counter = 0;

    printf("Enter X and Y: ");
    if (scanf("%d %d", &x, &y) != 2)
        return 1;

    printf("Germain Prime Numbers in the Range: ");
    for (i = x; i <= y; i++) {
        if (isPrime(i) && isPrime(2 * i + 1)) {
            counter++;
            if (counter > 1)
                putchar('-');
            printf("%d", i);
        }
    }
    printf("\n");
    return 0;   
}

如果你不能使用函数，这是一个奇怪的要求，你可以扩展 main里面的代码。功能:

#include <stdio.h>

int main() {
    int x, y, counter = 0;

    printf("Enter X and Y: ");
    if (scanf("%d %d", &x, &y) != 2)
        return 1;

    printf("Germain Prime Numbers in the Range: ");
    for (int n = x; n <= y; n++) {
        int isprime = (n >= 2);
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                isprime = 0;
                break;
            }
        }
        if (isprime) {
            int isgermain = 1;
            for (int i = 2, n2 = 2 * n + 1; i <= n2 / i; i++) {
                if (n2 % i == 0) {
                    isgermain = 0;
                    break;
                }
            }
            if (isgermain) {
                counter++;
                if (counter > 1) {
                    putchar('-');
                }
                printf("%d", n);
            }
        }
    }
    printf("\n");
    return 0;   
}

这是使用简单的 Eratosthenes 筛子的替代方法。它在不到 30 秒的时间内找到所有低于 109 的 Sophie Germain 素数:

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

int main(int argc, char *argv[]) {
    int x, y, counter = 0;

    if (argc > 1) {
        x = y = strtol(argv[1], NULL, 0);
        if (argc > 2) {
            y = strtol(argv[2], NULL, 0);
        }
    } else {
        printf("Enter X and Y: ");
        if (scanf("%d %d", &x, &y) != 2)
            return 1;
    }
    int max = 2 * y + 1;
    unsigned char *composite = calloc(max + 1, 1);
    if (composite == NULL) {
        printf("out of memory\n");
        return 1;
    }
    composite[0] = 1;
    composite[1] = 1;
    for (int p = 2; p * p <= max; p++) {
        if (composite[p])
            continue;
        for (int i = p * p; i <= max; i += p)
            composite[i] = 1;
    }
    for (int p = x; p <= y; p++) {
        if (composite[p] || composite[2 * p + 1])
            continue;
        counter++;
        //printf("%d\n", p);
    }
    free(composite);
    printf("Count of Germain primes between %d and %d: %d\n", x, y, counter);
    printf("approximation for count to %d: 10+1.6*N/log(N)²=%.2f\n",
           y, 10 + 1.6 * y / (log(y) * log(y)));
    return 0;
}