用C++写一段判断质数的最快方法

以下是一个用C语言编写的判断质数的最快方法：

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

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    int i = 5;
    int w = 2;
    while (i * i <= n) {
        if (n % i == 0) {
            return false;
        }
        i += w;
        w = 6 - w;
    }
    return true;
}

int main() {
    int num;
    printf("请输入一个数字：");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d 是质数\n", num);
    } else {
        printf("%d 不是质数\n", num);
    }
    return 0;
}

该算法使用了优化后的试除法，只需要判断小于等于根号n的奇数是否是n的因子即可。这种方法的时间复杂度约为O(√n)。

相关问题

写一个C++筛1到10000素数代码

### 回答1：

答：
我可以为您提供一个简单的C程序，以筛选1到10000之间的素数：#include <stdio.h>

int main()
{
int i, j;

printf("从1到10000之间的素数有：\n");
for(i=2; i<=10000; i++)
{
for(j=2; j<=i-1; j++)
{
if(i%j==0)
break;
}
if(i==j)
printf("%d\t", i);
}
printf("\n");

return 0;
}

### 回答2：
这是一个用C语言编写的筛选素数的代码。它使用埃拉托斯特尼筛法，通过遍历从2到10000的所有数字，将非素数的倍数标记为合数。最后，输出所有未被标记的数字，即为所有的素数。

#include <stdio.h>

int main() {
    int n = 10000;
    int prime[10001] = {0};  // 0表示数字为素数，1表示数字为合数

    for (int i = 2; i <= n; i++) {
        if (prime[i] == 0) {  // 当找到素数时
            for (int j = i * 2; j <= n; j += i) {  // 将该素数的倍数标记为合数
                prime[j] = 1;
            }
        }
    }

    printf("1到%d的素数为：\n", n);
    for (int i = 2; i <= n; i++) {
        if (prime[i] == 0) {
            printf("%d ", i);
        }
    }

    return 0;
}

这段代码首先创建了一个包含10001个元素的数组`prime`，用于标记数字是否为素数。然后，通过从2开始循环到10000，如果当前数字为素数，则将其倍数全部标记为合数。最后，遍历数组，输出未被标记为合数的数字，即为所有的素数。以上就是一个简单的筛选素数的C语言代码。

### 回答3：
筛素数（Sieve of Eratosthenes）是一种高效的算法，可以快速找出给定范围内的所有素数。下面是使用C语言编写的筛素数代码，实现1到10000之间的素数筛选：

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

#define MAX_NUM 10000

void sieveOfEratosthenes(bool isPrime[], int n) {
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

int main() {
    bool isPrime[MAX_NUM+1];
    for (int i = 2; i <= MAX_NUM; i++) {
        isPrime[i] = true;
    }

    sieveOfEratosthenes(isPrime, MAX_NUM);

    printf("1到10000之间的素数为:\n");
    for (int i = 2; i <= MAX_NUM; i++) {
        if (isPrime[i]) {
            printf("%d ", i);
        }
    }

    return 0;
}

以上代码首先定义了一个布尔数组`isPrime`，用于表示某个数是否为素数。然后通过`sieveOfEratosthenes`函数，按照筛素数的算法，将不是素数的数标记为`false`。最后，在`main`函数中打印出范围内所有的素数。

运行该代码，将会输出1到10000之间的素数。