C语言 求素数、闰年以及最小公倍数最大公约数

目录

一、求100-200之间的素数

1.第一种写法

2.第二种写法以及效率优化

二、求1000-2000之间的闰年

三、最大公约数和最小公倍数

---

一、求100-200之间的素数

100-200之间的素数以及个数。

素数又叫质数（只能被1和自身整除的数）。

1.第一种写法

int main()
{
	int a = 0;
	int b = 0;
	int i = 0;//i记录个数
	for (a = 100; a <= 200; a++)
	{
		for (b = 2; b <= a; b++)
		{
			if (a % b == 0)
				break;
		}
		if (a == b)
		{
			printf("%d ", a);
			i++;
		}
	}
	printf("%d ", i);
	return 0;
}

2.第二种写法以及效率优化

创建一个变量来监视循环，也可以达到相同的效果

不同逻辑，相同效果

当然这串代码还可以优化

int main()
{
	int a = 0;
	int b = 0;
	for (a = 100; a <= 200; a++)
	{
		int c = 1;//用c来判断
		for (b = 2; b < a; b++)
		{
			if (a % b == 0)
			{
				c = 0;
				break;
			}
		}
		if (c == 1)
			printf("%d ", a);
	}
	return 0;
}

int main()
{
	int a = 0;
	int b = 0;
	for (a = 101/*100改为101*/; a <= 200; a+=2)//把a++替换成a+=2
	{
		int c = 1;
		for (b = 2; b <= sqrt(a)/*a优化成开平方a*/; b++)
		{
			if (a % b == 0)
			{
				c = 0;
				break;
			}
		}
		if (c == 1)
		{
			printf("%d ", a);
		}
	}
	return 0;
}

这样一改，虽然代码变长了但效率比之前提升了很多

因为既然是素数，a就不可能是偶数，所以直接初始值100改成101，a++换成a+=2，直接跳过了一半的值，相当于把效率提高了一倍。

b<a改成b<=sqrt(a)

sqrt是开平方函数，意为a的开平方，引用头文件<math.h>

假设有一个数为m

那么m的两个乘积至少有一个小于等于m的开平方。

16，开平方为4，那么他的所有乘积中肯定至少有一个小于等于4。

所以b<a改成b<=sqrt(a)整个循环效率又直接提高一个开平方。

简直就是简直了，兄弟们。

二、求1000-2000之间的闰年

闰年（可以被4整除且不能被100整除，或者能被400整除）。

所以就可以用到我们c语言中的两个操作符&&（并且）和||（或者）来做简化。

int main()//1000-2000之间的闰年，并记录个数
{
	int a = 0;
	int b = 0;//记录个数
	for (a = 1000; a <= 2000; a++)
	{
		if ((a % 4 == 0 && a % 100 != 0) || a % 400 == 0)
		{
			printf("%d ", a);
			b++;
		}
	}
	printf("%d ", b);
	return 0;
}

 最终结果

三、最大公约数和最小公倍数

先求最大公约数

如过b比a大，则a%b等于a，然后进入循环b赋给a，a%b赋给b(所以a%b，如果b>a会直接大小调换)

所以就没必要提前把最大值赋给a,最小值赋给b

a % b，结果赋给t，然后最大值%t，直到为0，跳出循环，此时b就是最大公约数

跳出循环代入公式最小公倍数为两数之积/最大公约数

ab乘积在循环之前写入赋给c，然后出循环直接c除最大公约数即为最小公倍数

int main()//最小公倍数等于a*b/最大公约数
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	int t = 0;
	int c = a * b;//最大公约数（两数之积/最大公约数）,所以在ab改变之前先乘一次
	while (t = a % b)
	{
		a = b;
		b = t;
	}
	c = c / b;
	printf("%d ", c);
	return 0;
}