C&C++ 查找范围内的素数- 编程源码 -卓越飞翔博客

#incliude <stdio.h>
void test6();
int main(){
test6();
return 0;
}
void test6(){
printf("\n==================================测试6.1==================================\n");

unsigned long xx = 2, n = 2, sign = 0, count = 1;
do {
sign = 0;//标志=0
for (n = 2; n < xx; n++) {//厉遍所有2到xx-1，即除1和自身外不能被其他整除的数
if (xx % n == 0) {//xx与n求余，厉遍所有n能整除xx的数
sign++;//能整除sign标志+1
break;//退出循环
}
}

if (!sign)//判断标志是否=0，这个数是整数，count计数+1
printf("%d ", count++);
xx++;
// if(count%4==0)printf("\n");
} while (xx <= 1000);//3到10000的素数
printf("\n==============%d以内共有%d个素数==============\n", 10000, count);
}

这段代码已经能够完成其功能，但是还有一些可以进行优化的地方：

在循环中，如果一个数能被2整除，那么它就不可能是素数，可以直接排除。
在判断一个数是否为素数时，只需要判断它是否能被比它小的素数整除即可，因为如果它能被比它大的素数整除，那么这个大的素数一定是由比它小的素数乘得，因此比它小的素数已经被检查过了。
可以做如下代码改进：

#include <stdio.h>

void test6();

int main() {
test6();
return 0;
}

void test6() {
printf("\n==================================测试6.1==================================\n");

int count = 1;
printf("%d ", count++); // 2是最小的素数，先输出2

for (int i = 3; i <= 1000; i += 2) { // 只检查奇数是否为素数，偶数除了2都不可能是素数
int is_prime = 1; // 假设当前数为素数

for (int j = 3; j * j <= i; j += 2) { // 只检查比当前数小的奇数是否为因子
if (i % j == 0) { // 如果能整除，那么当前数不是素数
is_prime = 0;
break;
}
}

if (is_prime) {
printf("%d ", count++); // 输出素数，并将计数器加1
}
}

printf("\n==============%d以内共有%d个素数==============\n", 1000, count - 1);
}

相关推荐