c - 在 C 中打印 0 到 1,000,000 之间的素数

Question

我正在尝试编写一个递归函数来打印 0 到 1,000,000 之间的所有素数:

#include <stdio.h>

int isPrime(int);
int globalChk; //Global Variable

int main(){

    printf("2\n");

    int i;

    for(i=3;i<1000000;i++){

        globalChk = i/2;

         if(isPrime(i)==1){
             printf("%d",i);
             printf("\n");
         }
     }

    return 0;
}

int isPrime(int num){
    if(globalChk==1){
        return 1;
    }
    else{
        if(num%globalChk==0) {
            return 0;
        }
        else {
        globalChk = globalChk-1;
        isPrime(num);
        }
    }
}

目前它似乎只打印 2 和 3 而没有其他内容。我似乎无法发现问题。它可能是全局变量。

Answer 1

首先

所有质数都等于平方根

所以你可以通过以下方式进行外循环

int n=sqrt(1000000);
for(int i=3;i<=n;i++)
{
}

您可以通过以下方式改进isPrime函数

bool isPrime(int n) {

    // Corner cases

    if (n <= 1)  
        return false;
    if (n <= 3)
        return true;
    // This is checked so that we can skip 
    // middle five numbers in below loop

    if (n%2 == 0 || n%3 == 0) 
        return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

哪个更快