C 中的质数程序 [英] Prime number program in C

问题描述

这个程序应该打印前 x 个质数，但我注意到它打印了一些非质数，例如 27 或 35.我一直在看它几个小时，似乎没有任何东西弹出.所以，如果你知道出了什么问题，请告诉我.

This program is supposed to print the first x prime numbers, but I noticed that it was printing some non-prime numbers, such as 27 or 35. I've been looking at it for hours and nothing seems to pop up. So please, if you know what's wrong, tell me.

#include <stdio.h>
int main(){
    int i=0, cont=2, prim=2, quant;
    printf("Insert number of prime numbers you wish: ");
    scanf("%d", &quant);
    printf("The first %d prime numbers are:\n", quant);
    while(i<quant){
        if(prim%cont!=0 && (cont>1 && cont<prim)){
            cont++;
        }
        else if(prim%cont==0 && (cont>1 && cont<prim)){
            prim++;
        }
        else if(prim%cont==0 && cont==prim){
            printf("%d\n", prim);
            prim++;
            cont=2;
            i++;
        }
    }
    return 0;
}

---

更新

哇，好吧，所以 7 年后人们仍然偶然发现这个问题.在过去的 7 年里，我的编码能力有所提高，现在我看到了这个程序是多么低效.以防万一有人试图为此找到解决方案并偶然发现此问题，这里提供了三个更简单、更好的解决方案，以及它们的工作原理.

Wow, ok, so after 7 years people still stumble upon this question. In the last 7 years my coding ability has improved somewhat, and now I see how inefficient this program was. Just in case anyone might be trying to find the solution for this and the stumble upon this, here are three solutions much easier and better, and why they work.

解决方案 1:第一个解决方案也非常低效，但它有效，而且很容易理解.基本上你要做的就是检查每个达到上限的数字是否是素数.为此，只需检查它是否可以被任何不超过其平方根的数整除.

Solution 1: This first solution is very inefficient too, but it works, and is pretty simple to understand. Basically what you have to do is check if each number up to the upper limit is prime or not. To do so, just check if it is divisible by any number up to its square root.

为什么是平方根?因为平方根的平方等于这个数，这意味着如果这个数不能被它的平方根整除，那么它就不能被它上面的任何数整除，至于要被它整除，就需要乘以一个较小的数.比如36的平方根是6，36可以被9整除，因为9*4=36.但是由于 9 大于 6(即平方根)，因此乘以 9 得到的数为 36，因此，我们已经看到它不是素数，因为我们已经检查过 36 可以被整除4. 话虽如此，如果一个数的平方根以下没有数是该数的自然被除数，则该数是素数.

Why its squared root? Because the square root squared is equal to the number, which means that if the number was not divisible up to its square root, it won't be divisible by any number above it, as for it to be divisible by it, it needs to multiply by a smaller number. For example, the squared root of 36 is 6, and 36 is divisible by 9, as 9*4=36. But since 9 is above 6 (which is the squared root), the number that multiplied by 9 gives us 36 is below, and as such, we have already seen that it is not prime, as we have already checked that 36 is divisible by 4. This being said, if no number below the squared root of a number is a natural dividend of the number, than that number is prime.

#include <stdio.h>

int isPrime(int num) {
    for (int i = 2; i*i <= num; i++) {
        if (num%i==0) {
            return 0;
        }
    }
    return 1;
}

void getPrimes(int num) {
    int cont = 0;
    for (int i = 2; cont < num; i++) {
        if (isPrime(i)==1) {
            printf("%d\n", i);
            cont++;
        }
    }
}

int main() {
    int quant;
    printf("Insert number of prime numbers you wish: ");
    scanf("%d", &quant);
    printf("The first %d prime numbers are:\n", quant);
    getPrimes(quant);
    return 0;
}

这是低效的，因为我们正在检查数字是否可以被不会影响的数字整除(在下一个解决方案中将详细介绍).

This is inefficient as we are checking if the number is divisible by numbers that won't influence (more on this in the next solution).

解决方案 2:在我认为更优雅的第二个解决方案中，我们使用了算术基本定理，它指出任何大于 1 的数要么是素数本身，要么可以通过分解为素数的乘法来表示.这意味着如果一个数能被一个非素数整除，它也能被组成它的素数整除，因此我们只需要检查这个数是否能被比它本身小的素数整除.为此，我们将质数存储在一个数组中.

Solution 2: In this second solution, which is more elegant in my opinion, we give use to the Fundamental Theorem of Arithmetic, which states that any number greater than 1 is either a prime number itself, or can be represented by factorizing into the multiplication of prime numbers. This means that if a number is divisible by a non prime number, it is also divisible by the prime numbers that make it up, and thus we only need to check if the number in question is divisible by smaller prime numbers than itself. For this purpose, we store the prime numbers in an array.

#include <stdio.h>

void getPrimes(int num) {
    int primes[num];
    int cont = 1;
    primes[0] = 2;
    int current = primes[cont-1]+1;
    while (cont < num) {
        int before = current;
        for (int i = 0; i < cont; i++) {
            if (current%primes[i]==0) {
                current++;
                break;
            }
        }
        if (before == current) {
            primes[cont] = current;
            cont++;
            current++;
        }
    }
    for (int i = 0; i < cont; i++) {
        printf("%d ", primes[i]);
    }
    printf("\n");
}

int main() {
    int quant;
    printf("Insert number of prime numbers you wish: ");
    scanf("%d", &quant);
    printf("The first %d prime numbers are:\n", quant);
    getPrimes(quant);
    return 0;
}

解决方案 3:这个最终的解决方案是上述两者的混合.解决方案 1 检查不是素数的数字，具有冗余性，解决方案 2 检查平方根以上的数字，如果较小的数字不是，则永远不会是被除数.在这个解决方案中，我们检查这个数是否只能被平方根以下的素数整除.

Solution 3: This final solution is a mix of the two above. Solution 1 checked numbers that weren't prime, having redundancy, and the solution 2 checked numbers above the square root, which can never be a dividend if the smaller numbers aren't. In this solution, we check if the number is divisible only by prime numbers below the squared root.

#include <stdio.h>

void getPrimes(int num) {
    int primes[num];
    int cont = 1;
    primes[0] = 2;
    int current = primes[cont-1]+1;
    while (cont < num) {
        int before = current;
        for (int i = 0; (i < cont && primes[i]*primes[i] <= current); i++) {
            if (current%primes[i]==0) {
                current++;
                break;
            }
        }
        if (before == current) {
            primes[cont] = current;
            cont++;
            current++;
        }
    }
    for (int i = 0; i < cont; i++) {
        printf("%d ", primes[i]);
    }
    printf("\n");
}

int main() {
    int quant;
    printf("Insert number of prime numbers you wish: ");
    scanf("%d", &quant);
    printf("The first %d prime numbers are:\n", quant);
    getPrimes(quant);
    return 0;
}

比较每个算法对 100 个素数的执行时间，我们得到如下结果

Comparing the execution times of each algorithm for 100 prime numbers, we obtain the following results

<头>

算法一	算法二	算法3
0.048 毫秒	0.068 毫秒	0.039 毫秒

与需要 0.599 ms 的原始帖子的算法相比，这些新解决方案中的每一个都更有效(最坏的情况下提高了 10 倍左右)，并且实际计算了实际值.

Comparing to the algorithm of the original post which takes 0.599 ms, every one of these new solutions is more efficient (the worst being around 10x better), and actually calculates the real values.

推荐答案

试试这个

#include<stdio.h>

int prime(int n)
{
    int i, j, len=1, brk=0;
    int list[200]={2};
    for(i=2; i<=n; i++)
    {
        for(j=0; j<len; j++)
        {
            if(i%list[j]==0){
                brk=1;
                break;
            }
            else
            {
                brk=0;
            }
        }
        if(brk==0)
        {
            list[len]=i;
            len++;
        }
    }
    for(i=0; i<len; i++)
        printf("%d ",list[i]);
}

main()
{
    int i, n;
    scanf("%d",&n);
    prime(n);
}

这篇关于C 中的质数程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！