C语言中求质数的三种方法：
1.试除法，根据质数的定义，对每个数字no进行（2~no-1）的试除
2.排除偶数法，2的倍数（除2之外），都不是质数
3.排除偶数法的基础上，对奇数进行奇数的试除
4.在奇数里面，判断no能否被 小于no的质数 整除
5.使用math函数的sqrt,试除法的改进，对数字进行（2~sqrt(no)）的试除
1.试除法：计算1~1000以内的质数
方法1：常规遍历
#include
int main() {
int i, no;
unsigned long counter = 0;
for (no = 2; no <= 1000; no++) {
for (i = 2; i < no; i++) {
counter++;
if (no % i == 0)
break;
}
//如果最终的i==no,说明一定是质数
if (no == i)
printf("%d\n", no);
}
printf("乘除运算的次数：%lu\n", counter);
return 0;
}
2.排除偶数法：计算1~1000以内的质数
#include
int main() {
int i, no;
unsigned long counter = 0;
//单独打印no=2
no = 2;
printf("%d\n", no++);
//此时for循环中，no=3开始，步长调整为2
//过滤掉除2之外的偶数，它们都不是质数
for (; no < 1000; no += 2) {
for (i = 2; i < no; i++) {
counter++;
if (no % i == 0)
break;
}
if (no == i)
printf("%d\n", no);
}
printf("乘除运算的次数:%lu\n", counter);
return 0;
}
3.排除偶数法的基础上，对奇数进行奇数的试除
#include
int main() {
int i, no;
unsigned long counter = 0;
no = 2;
printf("%d\n", no++);
//从no=3开始，步长为2
for (; no <= 1000; no += 2) {
//在奇数里面使用奇数进行试除
for (i = 3; i < no; i += 2) {
counter++;
if (no % i == 0)
break;
}
if (no == i)
printf("%d\n", no);
}
printf("乘除运算的次数:%lu\n", counter);
return 0;
}
4.在奇数里面，判断no能否被 小于no的质数 整除
#include
int main() {
int i, no;
int prime[500];//先排除掉偶数
int ptr = 0;
unsigned long counter = 0;
//prime[0]=2,prime[1]=3,ptr=2
prime[ptr++] = 2;
prime[ptr++] = 3;
//no=5,对奇数进行遍历，
for (no = 5; no <= 1000; no += 2) {
//判断能否被小于no的质数整除
for (i = 1; i < ptr; i++) {
counter++;
if (no % prime[i] == 0)
break;
}
if (ptr == i)
prime[ptr++] = no;
}
for (i = 0; i < ptr; i++)
printf("%d\n", prime[i]);
printf("乘除运算的次数:%lu\n", counter);
return 0;
}
5.
#include
int main() {
int i, no;
int prime[500];
int ptr = 0;
unsigned long counter = 0;
prime[ptr++] = 2;
prime[ptr++] = 3;
for (no = 5; no <= 1000; no += 2) {
int flag = 0;
for (i = 1; counter++, prime[i]*prime[i] <= no; i++) {
counter++;
if (no % prime[i] == 0) {
flag = 1;
break;
}
}
if (!flag)
prime[ptr++] = no;
}
for (i = 0; i < ptr; i++)
printf("%d\n", prime[i]);
printf("乘除运算的次数:%lu\n", counter);
return 0;
}