C++程序寻找给定区间内的质数

什么是质数？

质数是指除了1和它本身以外，不能被其他正整数整除的数。例如，2、3、5、7、11、13等都是质数。

如何判断一个数是质数？

判断一个数是否是质数，最简单的方法就是在2到该数的平方根范围内逐一检查是否存在约数。如果不存在，那么这个数就是质数。

C++代码实现：

bool isPrime(int n){
    if(n<=1) return false;  //如果小于等于1，则不是质数
    int sqrtn=sqrt(n);  //求该数平方根
    for(int i=2;i<=sqrtn;i++){
        if(n%i==0) return false;  //如果能被2到平方根之间的任意一个数整除，则不是质数
    }
    return true;  //否则是质数
}

如何寻找给定区间内的质数？

方法一：暴力枚举

暴力枚举是最基本的方法，即对于区间内的每个数，逐一判断是否是质数。

C++代码实现：

for(int i=low;i<=high;i++){
    if(isPrime(i)){
        cout<<i<<endl;
    }
}

方法二：筛法

筛法是一种更加高效的方法，其原理是先将区间内所有的数标记为质数，然后从小到大遍历，将其倍数标记为合数，最终留下的就是质数。

C++代码实现：

void findPrimes(int low, int high){
    int prime[high+1];  //定义数组，用来标记质数和合数，0表示质数，1表示合数
    memset(prime, 0, sizeof(prime));  //将质数标记全部初始化为0
    for (int i=2;i<=high;i++){
        if (prime[i] == 0){  //如果该数为质数
            if (i >= low) cout<<i<<endl;  //如果在区间内，则输出
            for (int j=i+i;j<=high;j+=i){  //将该数的倍数标记为合数
                prime[j] = 1;
            }
        }
    }
}