logo标签列表

用户输入范围内打印德国质数的C程序

c
3

给定用户输入的整数 X 和 Y（假设 X < Y），编写程序将 X 到 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;   
}

有人能告诉我错在哪里吗？

编辑：我不应该使用用户创建的函数。

3
你的代码包含一个 isPrime() 函数，为什么不使用它？编辑：另外，如果你想要合理的结果，if (2 * i + 1 % k == 0) 应该改为 if ((2 * i + 1) % k == 0)。 - r3mainer
2
在第一次迭代中，for (j = 1; j <= i; j++) {if (i % j == 0) {是正确的。 - chux - Reinstate Monica
2
for (int i = 2; i <= n/i; i++) runs much faster than for (int i = 2; i < n; i++) - chux - Reinstate Monica
1
alpermakaveli，你的要求是“将所有德国素数添加到一个数组中”，但是在你的代码中并没有为它们创建数组，只有输出。这是真正的要求吗？ - chux - Reinstate Monica
1
另外值得注意的是，这些质数是以Sophie Germain命名的。 - chux - Reinstate Monica
显示剩余4条评论
5个回答
4

你的代码太复杂了，主循环需要简化。此外，输出结果与示例不一致。

以下是问题：

  • 循环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;   
}

这里是使用一种简单的埃拉托斯特尼筛法的另一种方法。它可以在不到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;
}
实际上我不应该使用像isPrime这样的函数。我认为有人从codeshare中更改了它。 - notorious
最终我修复了我的程序，但无法将那些Germain素数添加到数组中。我不知道如何创建这样的循环，因为我不知道程序会获得多少个Germain素数。 - notorious
1
对于小于 N 的 Sophie Germain 素数的数量，您可以使用近似的上界 10+1.6*N/log(N)²。我有一个优美的证明，但是这个评论太简洁了，无法包含它 :) - chqrlie
3
“问题”在于您从未重置 counter2 变量，并且 if (2 * i + 1 % k == 0)需要括号。真正的问题是，您已经实现了isPrime功能三次，而不是只实现它一次并调用两次，这导致您迷失在不必要的复杂性中。
2
还要提示使用括号 if (2 * i + 1 % k == 0)。 - chqrlie
是的，我添加了那个括号，但我不应该使用用户创建的函数。isPrime是由我在分享代码的网站上的其他人添加的。 - notorious
谁告诉你不要为此定义一个函数就是错的，教你坏习惯。检查质数是否为德国素数的方法肯定比每个数字都检查n是否为质数并检查2n+1是否为质数的算法更好（例如首先在某个范围内找到所有质数，然后检查2n+1条件），但这些更好的方法都无法避免定义一个函数。 - mCoding
我们在讲座中没有看到函数，这就是为什么它被禁止的原因。我试图先找到质数，然后检查2p+1的质性。然而，作为一个初学者，我失败了。 - notorious
@alpermakaveli：“我们在讲座中还没有看到函数”的意思是您正在编写一个名为int main()的_function_。所以您至少见过一个特殊的函数。 - chux - Reinstate Monica
是的，但我的意思是用户创建的函数。 - notorious
1

没有太多时间来调试您的代码。但是您可以运行以下代码：

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

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

bool isGermanPrime(int n)
{
    return isPrime(n) && isPrime(n*2+1);
}

int main()
{
    int x, y;
    // printf("Please enter x and y values:\n\a");
    // scanf("%d %d", &x, &y);
    x = 2;
    y = 15;

    for (int i = x; i <= y; i++)
    {
        if (isGermanPrime(i))
            printf("%d ", i);
    }
    return 0;
}

//OUTPUT
2 3 5 11
我不应该使用由用户创建的函数。isPrime是从我分享代码的网站上添加的其他人提供的。 - notorious
你需要自己编写isPrime函数，如果我为你编写一个也是不可接受的。 - Jasen
是的，那肯定是不可接受的。我只是在这里找出我的错误并修复它。 - notorious
1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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

int main() {
    int x, y;

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

    for (int p = x; p < y; p++) {
        if (isPrime(p) && isPrime(2 * p + 1)) {
            printf("%d is a germain prime number\n", p);
        }
    }

    return 0;
}
我不应该使用用户创建的函数。isPrime是由我在共享我的代码的网站上添加的其他人创建的。 - notorious
好的，抱歉我不知道。我以为你写了这个函数。 - Carl Schader
那是我的错，忘记删除它了。 - notorious
有没有可能不用它？ - notorious
1

编写程序，将范围在X到Y之间的所有Germain素数添加到数组中，并在屏幕上打印该数组中的元素。"并且"我不应使用用户创建的函数。这就是它。

#include <stdio.h>

#define SIZE 100

int main() {

    int x, y, germ, prime, gPrime;
    int n[SIZE], count = 0, i, j;

    scanf("%d%d", &x, &y);

    if( x < 3 ) {

        n[0] = 2;
        ++count;
        x = 3;
    }
    else if( !(x % 2) ) {
        
        ++x;
    }

    for(i = x; i <= y; i += 2) {

        prime = 1;
        gPrime = 1;
    
        for(j = 3; j < i; y += 2) {
        
            if( !(i % j) ) {
            
                prime = 0;
                break;
            }
        }
    
        if( prime ) {
    
            germ = 2 * i + 1;
        
            for(j = 3; j < germ; j += 2) {
            
                if( !(germ % j) ) {
                
                    gPrime = 0;
                    break;
                }
            }
        
            if( gPrime ) {
            
                n[count] = i;
                ++count;
            }
        } // end outer if
    }

    for(i = 0; i < count; i++) {
    
        printf("%d ", n[i]);
    }

    return 0;
}

注意：我在手机上使用的编译器有时间限制，无法看到输出。希望程序能够正常运行。
它没有输出，但给了我灵感，谢谢。 - notorious
哦，我以为是因为时间限制的原因。不管怎样，你非常受欢迎。 - anotherOne
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接