【c语言】闰年判断，素数（质数）判断，最大公约数判断_为什么判断为闰年需要写while 不可以直接判断吗

一、打印1000年到2000年的闰年

1、什么是闰年？

        正常年份是平年的2月有28天，因为一年准确来说有365.25天，每四年就会多一天，为了记录这多的一天，我们的闰年2月一共有29天，所以每四年会有一个闰年。

        由于科学家发现一年准确来说有365.2422天，我们之前多算了0.0078天，相当于每400年就多加了3天，所以我们要400年中去掉三个闰年，保留一个闰年，于是1600是闰年，1700，1800，1900是平年，2000是闰年，2100，2200，2300是平年，2400是闰年。。。以此类推，我们发现这些年份都可以被400除尽。

2、所以在c语言中如何计算闰年呢？

        我们分为两类，非整百年和整百年，一类是可以被4除尽，同时非整百年不能被100除尽，另一类是可以被400除尽的整百年。因为两类没有重叠的计算，不会有同时成立的情况，所以两类之间是或者的关系，有一个成立即是闰年。这样逻辑就很清晰了。

         四年一闰，百年不闰，四百年再闰。

        c语言中逻辑操作符：逻辑与&&即全真为真，一假则假，逻辑或||即有真则真，全假则假。

3、while循环实现

#include <stdio.h>
 
int main()
{
	int year = 1000;
	while (year <= 2000)
	{
		if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
			printf("%d ", year);
		year++;
	}
	return 0;
}

4、for循环实现

#include <stdio.h>
 
int main()
{
	int year = 0;
	for (year = 1000; year <= 2000; year++)
	{
		if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
			printf("%d ", year);
	}
 
	return 0;
}

5、函数实现

#include <stdio.h>
 
//函数有传参，有返回值，函数名要有意义，函数内if和else要写清楚
int is_leap_year(int y)
{
	if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
		return 1;
	else
		return 0;
}
 
 
int main()
{
	int year = 0;
	for (year = 1000 ; year <= 2000 ; year+=4)
	{
		int ret = is_leap_year(year);//用ret来接受函数的返回值，再判断ret值
		if (ret == 1)
			printf("%d ",year);
	}
	return 0;
}

6、注意

        我们可以把循环调整部分写成year+=4，可以减少代码数据处理量。

        注意if条件里面要写==来判断相等，如果写=则是赋值的意思。

        自查：注意打印结果中，1200，1600是闰年打印，而1100，1300，1400，1500等不是闰年，不可以出现在打印结果中。

二、打印100到200的素数（质数）

1、原理（试除法）

        素数是只能被1和它本身整除的数字，一个数n，除去1和n，我们只要用2—n-1的数字除一下，如果找到一个整除数，那么n不是素数，如果找不到一个整除数，那么n就是素数。

2、待优化的版本

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
 
int main()
{
	int num = 0;
	scanf("%d", &num);
	int flag = 1;
	int i = 0;
 
	for (i = 2;i < num;i++)//产生2-n-1的数字
	{
		if (num % i == 0)
		{
			flag = 0;//有可以除尽，不是素数
			break;
		}
	}
	if (flag == 1)
		printf("是素数\n");
	else
		printf("不是素数\n");
	return 0;
}

3、优化后的版本

       1， 一个合数m可以写成a*b，那么a，b至少有一个数字小于等于根号m，比如16=2*8，16=4*4，2和4都小于等于根号16，即4。

        如果在2—根号m找不到可以整除的数，那么根号m后面也不会有了，比如m=101，我们在2—10找不到可以整除的数，所以它是素数。

        根号sqrt（）的使用要包含头文件math.h 。

       

        2，可以产生num100-200的数字，num可以从101开始，num+=2，因为偶数不可能是素数，可以从源头上减少一半的数据。

       

         3，注意flag要定义在num循环内部，否则只会打印101和103，105不是素数，flag一旦改成0，没有机会初始化为1，不会再继续打印后面的素数了。

#include <stdio.h>
#include <math.h>
 
int main()
{
	int num = 0;
	int i = 0;
 
	for (num = 101; num < 200; num += 2)
	{
		int flag = 1;//假设num是素数
		for (i = 2; i < sqrt(num); i++)//产生2-根号num的数字
		{
			if (num % i == 0)
			{
				flag = 0;//有可以除尽，不是素数，跳出循环，再判断下一个num
				break;
			}
		}
		if (flag == 1)
			printf("%d ", num);
	}
	return 0;
}

3、用函数实现

#include <stdio.h>
#include <math.h>
 
int is_prime(int n)
{
	int i = 0;
	for (i = 2;i <=sqrt(n);i++)//注意i要从2开始，不能从1开始
	{
		if (n % i == 0)
			return 0;
	}
	return 1;
}
 
int main()
{
	int num = 0;
	for (num = 101;num < 200;num += 2)//只产生奇数
	{
		int ret = is_prime(num);
		if (ret == 1)
		{
			printf("%d ", num);
		}
	}
	return 0;
}

三、求最大公约数（试除法）

1、原理

        我们要找到两个数的 （最大+公约数）

        首先，因为两个数m，n的最大公约数不可能超过m和n中的较小值k，所以我们先找到较小值k，然后开始用n和m取余，k逐渐减小，如果有m和n同时可以整除，此时的k就是最大公约数。

       （公约数）公约数就是两个数都可以同时被k整除。

       （最大）因为n和m可能有多个公约数，我们要找的是最大的公约数，所以我们要从大到小找，k是依此减小的，于是找到的第一个公约数就是最大公约数。比如12和20的公约数有1，2，3，6，所以12和30的最大公约数是6。

2、代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
 
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d",&m,&n);
	int k = (m < n ? m : n);//k是m和n的较小值
 
	while(k > 0)
	{
		if (m % k == 0 && n % k == 0)//公约数就是两个数都可以同时被k整除
		{
			printf("m和n的最大公约数是%d", k);
			break;
		}
		k--;
	}
	return 0;
}

四、求最大公约数（辗转相除法）

1、原理

求288和123的最大公约数

用较大的数除以较小的数，上面较小的除数和得出的余数构成新的一对数，继续做上面的除法，直到出现能够整除的两个数，其中较小的数（即除数）就是最大公约数。

288➗123=2。。。42

123➗42=2。。。39

42➗39=1。。。3

39➗3=13

直到可以除尽，此时288和123的最大公约数是3，（288=3×96，123=3×41）

对应的程序

while（k=m%n）

{

        m=n；

        n=k；

}

最大公约数是n，k是余数为0的时候会跳出循环，while里面的表达式的结果是k非0为真，0为假时，不再循环，即m和n除尽时余数为0，不再辗转相除。

 2、代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
 
int main()
{
	int m = 0;
	int n = 0;
	int k = 0;
	scanf("%d %d", &m, &n);
 
	while (k = m % n)//表达式的结果k为0时不进入循环
	{
		m = n;
		n = k;
	}
	printf("m和n的最大公约数是%d", n);//除数n是最大公约数，此时余数k为0
	return 0;
}

 

如果输入值m比n小怎么办？

18➗24=0。。。18

24➗18=1。。。6

18➗6=3

第一二步就可以交换大小，之后可以正常求解，所以输入两个数可以不需要有先后大小顺序。

m和n有没有可能没有最大公约数呢？

不可能，比如3和4的最大公约数就是1，因为3和4只有一个公约数就是最大的，所以跳出while循环就只有一种情况k==0，直接打印n就可以了，不需要判断k！=0的情况。