在 C 语言中打印 0 到 1,000,000 之间的素数

Question

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

#include <stdio.h>
int isPrime(int);
int globalChk; //Global Variable
int main(){
    printf("2n");
    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;
}

哪个更快