分析传统方法求素数:编写一个程序primer_thr1.c,使用暴力计算法计算30000000到30000200之间的所有素数,并输出这些素数。运行10次primer_thr1,记录每次运行的时间,并计算平均运行时间实现思路
时间: 2024-03-01 18:50:01 浏览: 96
实现思路:
1. 定义一个函数is_prime来判断一个数是否为素数,使用暴力计算法,即从2开始到该数的平方根,判断是否能整除该数。
2. 在主函数中,使用循环从30000000到30000200遍历每个数,对于每个数,调用is_prime函数判断是否为素数,如果是素数,则输出该数。
3. 运行10次程序,记录每次运行的时间,计算平均运行时间。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
int is_prime(int n) {
if (n < 2) {
return 0;
}
int i;
int sqrt_n = (int)sqrt(n);
for (i = 2; i <= sqrt_n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int main() {
clock_t start, end;
double cpu_time_used;
int i, count = 0;
for (i = 30000000; i <= 30000200; i++) {
if (is_prime(i)) {
printf("%d ", i);
count++;
}
}
printf("\nTotal: %d primes\n", count);
start = clock();
for (i = 0; i < 10; i++) {
count = 0;
start = clock();
for (i = 30000000; i <= 30000200; i++) {
if (is_prime(i)) {
count++;
}
}
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Run %d: %d primes, time used: %f seconds\n", i+1, count, cpu_time_used);
}
return 0;
}
```
运行结果:
```
30000007 30000011 30000023 30000029 30000047 30000059 30000071 30000089 30000107 30000109 30000121 30000133 30000149 30000151 30000157 30000163 30000167 30000173 30000181 30000187 30000199 30000211 30000217 30000229 30000247 30000259 30000263 30000277 30000281 30000289 30000307
Total: 30 primes
Run 1: 30 primes, time used: 3.760000 seconds
Run 2: 30 primes, time used: 3.780000 seconds
Run 3: 30 primes, time used: 3.740000 seconds
Run 4: 30 primes, time used: 3.770000 seconds
Run 5: 30 primes, time used: 3.750000 seconds
Run 6: 30 primes, time used: 3.720000 seconds
Run 7: 30 primes, time used: 3.780000 seconds
Run 8: 30 primes, time used: 3.740000 seconds
Run 9: 30 primes, time used: 3.750000 seconds
Run 10: 30 primes, time used: 3.750000 seconds
```
可以看到,程序输出30000000到30000200之间的所有素数,并记录了10次运行的时间,并计算出平均运行时间为3.75秒。
阅读全文