[C++知识库]C语言实现1~100的素数

1.判断什么是素数？

只能被1和自身整除的数。

#include<stdio.h>
int main()
{
	int i;
	for(i = 2;i <= 100;i++)    //1不是素数
	{
		int j = 0;
		for(j = 2;j <= i;j++)    //从j->i取余，如果余数为0则不是素数，跳出循环
		{
			if(i%j == 0)
			{
				break;
			}
		}
		if(i == j)
		{
			printf("%d ",i);
		}
	}
	return 0;
}

算法优化：

判断素数的另一个方法是，对一个数i开平方，如果在小于该数的开平方数里有一个数对i取余==0，那么该数i就不是素数；

例：16=2*8=4*4；判断16是否为素数只需对4之前的数取余即可；

程序优化如下：

#include <stdio.h>
#include <math.h>
int main()
{
	int i = 0;
	for(i = 2;i <= 100;i++)
	{
		int j = 0;
		for(j = 2;j <= sqrt(i*1.0);j++)
		{
			if(i%j == 0)
			{
				break;
			}
		}
		if(j > sqrt(i*1.0))
		{
			printf("%d ",i);
		}
	}
	return 0;
}