素数:除了1和它本身以外再无其他因子
1、试除法:判断i是否时素数,则用2—>i-1个数去整除i,若可以整除,则说明i不是素数
int main()
{
int i = 0; //用i记录100-200之间的数
int count = 0; //用count统计100-200之间的素数个数
for (i = 100; i <= 200; i++)
{
int j = 0; //用j记录比i小的2—>i-1个数字
for (j = 2; j <i; j++) //j<i则为i-1个数字
{
if (i % j == 0) //如果i整数j,则说明i含有因子
{
break;//跳出for循环
}
}
//执行if有两种情况:1、break跳出。
//2、for循环不满足规则就j<i了,跳出,此时i为素数。
if (j == i) // j==i时说明将2—>i-1个数字均试完了,均不整除,则i为素数
{
count++;
printf("%d ", i);
}
}
printf("\ncount=%d\n",count);
return 0;
}
2、试除法的改进(增加算法的效率)
在i开根号之前若可以找到i的因子则i 不为素数。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main()
{
int i = 0;//用i记录100-200之间的数
int count = 0;//用count统计100-200之间的素数个数
for (i = 100; i <= 200; i++)
{
int j = 0;//用j记录比i小的2—>i-1个数字
for (j = 2; j <=sqrt(i); j++)//sqrt(i)也可以写为i/2,因为sqrt(i)一定小于i/2
{
if (i % j == 0)//如果i整数j,则说明i含有因子
{
break;//跳出for循环
}
}
if (j>sqrt(i))
{
count++;
printf("%d ", i);
}
}
printf("\ncount=%d\n",count);
return 0;
}
3、我们知道偶数一定不是素数,所以在判断 i 是否为素数时可以直接将偶数跳过。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main()
{
int i = 0;//用i记录100-200之间的数
int count = 0;//用count统计100-200之间的素数个数
for (i = 10; i <= 200; i+=2)//从101开始步长为2,跳过偶数
{
int j = 0;//用j记录比i小的2—>i-1个数字
for (j = 2; j <=sqrt(i); j++)
{
if (i % j == 0)//如果i整数j,则说明i含有因子
{
break;//跳出for循环
}
}
//执行if有两种情况:1、break跳出。
//2、for循环不满足规则就j<i了,跳出,此时i为素数。
if (j>sqrt(i))
{
count++;
printf("%d ", i);
}
}
printf("\ncount=%d\n",count);
return 0;
}