求素数、最大公约数和最小公倍数

求素数、最大公约数和最小公倍数

目录

一、素数

二、最大公约数

三、最小公倍数

一、素数

首先我们要知道什么是素数，然后才能进一步去求解，素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

求解思路：在这里举例从中寻找素数，并打印出来。

       在主函数中先把框架建好，先定义一个变量count=0，从之间寻找素数，在for循环中判断是否是素数，是素数count加1，统计一下之间总共几个素数，并且把素数全部打印出来。

       接着我们就自己定义一个函数，用来判断是否是素数，判断素数的方法是：用之间的某个数n去试除2到n-1之间的数，如果能整除说明不是素数，如果不能整除是素数。

代码如下：

#include <stdio.h>int is_prime(int n)
{//用n去试除2->n-1之间的数字，看看能不能整除int j = 0;for (j = 2; j < n; j++){if (n % j == 0){return 0;}}return 1;
}//如果是素数返回1，不是素数返回0
int main() 
{//打印100-200之间的素数int i = 0;int count = 0;for (i = 100; i <= 200; i++){//判断i是不是素数if (is_prime(i) == 1){printf("%d ", i);count++;}}printf("n素数的个数为：%d", count);return 0;
}

二、最大公约数

最大公约数是指：两个或多个整数共有约束中最大的一个。比如：12,16的公约数有1、2、4，其中最大的就是4。18,24的公约数有1、2、3、6，其中最大的就是6。

求解思路：在这里假设两个数中求最大公约数

        首先输入两个数a,b。然后定义一个变量Max为最大公约数，假设最大公约数Max就是a和b中较小的值，然后用a和b去同时整除最大公约数Max,如果能整除，那么Max就是这两个数的最大公约数，如果不能整除Max就减减，直到找出最大公约数再跳出循环。

代码如下：

#include <stdio.h>int main()
{int a = 0;int b = 0;scanf("%d %d", &a, &b);int Max = 0;//假设最大公约数Max是a和b的较小值if (a > b)Max = b;elseMax = a;while (1){if (a % Max == 0 && b % Max == 0){printf("最大公约数是：%dn", Max);break;}Max--;}return 0;
}

三、最小公倍数

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。比如：45,30的最小公倍数为90。

求解思路：在这里假设两个数中求最小公倍数

       介绍两种求最小公倍数的方法，方法（1）：首先输入两个数m,n。然后定义一个变量Min为最小公倍数，假设最小公倍数Min就是m和n中较大的值，然后用最小公倍数Min去整除m和n，如果可以同时整除说明是最小公倍数，如果不能整除就Min加加，直到找到最小公倍数。

代码如下：

#include<stdio.h>int main()
{int m = 0;int n = 0;scanf("%d %d",&m,&n);int Min = 0;//假设最小公倍数Min是m和n的较大的值if (m > n)Min = m;elseMin = n;while (1){if (((Min % m)==0) && ((Min % n)==0)){printf("%dn", Min);break;}Min++;}
}   

方法（2）：这种方法相对于上面的那种方法，运行速度会相对较快。思路是：假设用其中一个数m去整除另一个数n，如果能整除，说明m就是最小公倍数，如果不能整除，就让m整倍的增加，增加完之后再去整除n，直到找到最小公倍数。

代码如下：

#include <stdio.h>int main()
{int m = 0;int n = 0;scanf("%d %d", &m, &n);int i = 1;while (m * i % n != 0){i++;}printf("%dn", m * i);return 0;
}

希望能够帮助大家！加油！！！