c语言所有素数之和怎么编程

时间:2025-01-25 01:28:45 游戏攻略

要计算C语言中所有素数之和,可以使用以下几种方法:

方法一:穷举法

通过嵌套循环遍历所有数字,并检查每个数字是否为素数,然后将所有素数累加起来。这种方法的时间复杂度较高,但可以实现目标。

```c

include

int isPrime(int num) {

if (num <= 1) {

return 0;

}

for (int i = 2; i * i <= num; i++) {

if (num % i == 0) {

return 0;

}

}

return 1;

}

int sumOfPrimes(int lower, int upper) {

int sum = 0;

for (int i = lower; i <= upper; i++) {

if (isPrime(i)) {

sum += i;

}

}

return sum;

}

int main() {

int lower, upper;

printf("请输入区间的起始值: ");

scanf("%d", &lower);

printf("请输入区间的结束值: ");

scanf("%d", &upper);

int sum = sumOfPrimes(lower, upper);

printf("区间 %d 到 %d 之间的素数之和为: %d\n", lower, upper, sum);

return 0;

}

```

方法二:埃拉托斯特尼筛法

这是一种高效的求素数的方法,通过筛选掉合数来找到所有素数。

```c

include

include

include

void sieveOfEratosthenes(int n, bool prime[]) {

memset(prime, true, (n + 1) * sizeof(bool));

prime = prime = false;

for (int p = 2; p * p <= n; p++) {

if (prime[p]) {

for (int i = p * p; i <= n; i += p) {

prime[i] = false;

}

}

}

}

int sumOfPrimes(int n) {

bool prime[n + 1];

sieveOfEratosthenes(n, prime);

int sum = 0;

for (int i = 2; i <= n; i++) {

if (prime[i]) {

sum += i;

}

}

return sum;

}

int main() {

int n;

printf("请输入一个正整数: ");

scanf("%d", &n);

int sum = sumOfPrimes(n);

printf("小于等于 %d 的素数之和为: %d\n", n, sum);

return 0;

}

```

方法三:质数判定算法

使用更高效的质数判定算法,如Miller-Rabin素性测试,可以在较短时间内找到大量素数。