求最大公约数、最小公倍数、-蒲公英云

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

一、求两个数的最大公约数

解法一：

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d%d", &a, &b);
    int min = (a > b) ? b : a;//18 24
    int m = 0;
    //假设m就是最大公约数
    for (m = min; m >= 1; m--)
    {
        if (a % m == 0 && b % m == 0)
        {
            break;
        }
    }
    printf("最大公约数是：%d\n", m);
    return 0;
}

解法二：辗转相除法

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d%d", &a, &b);
    while (a % b != 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    printf("最大公约数为： %d\n",b);
    return 0;
}

二、求两个数的最小公倍数

//给定两个数，求这两个数的最小公倍数
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d%d", &a, &b);
    int max = a > b ? a : b;
    int m = 0;//假设m是a,b的最小公倍数
    for (m = max; m >= max; m++)
    {
        if (m % a == 0 && m % b == 0) {
            break;
        }
    }
    printf("最小公倍数为：%d\n",m);
    return 0;
}

三、求1000-2000年之间的闰年

首先要知道什么是闰年：
普通闰年：公历年份是4的倍数，且不是100的倍数的，为闰年（如2004年、2020年等就是闰年）。
世纪闰年：公历年份是整百数的，必须是400的倍数才是闰年（如1900年不是闰年，2000年是闰年）。
什么是闰年

int main()
{
    int year = 0;
    int cont = 0;
    for (year = 1000; year <= 2000; year++)
    {
        /*if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
        {
            printf("%d ", year);
            cont++;
        }*/
        if (year % 4 == 0) 
        {
            if (year % 100 != 0)
            {
                printf("%d ", year);
                cont++;
            }
        }
        if (year % 400 == 0)
        {
            printf("%d ", year);
            cont++;
        }
    }
    printf("\ncont = %d\n",cont);
    return 0;
}

四、判断100-200之间的素数

1、素数又叫质数。素数，指的是“大于1的整数中，只能被1和这个数本身整除的数”。

2、素数也可以被等价表述成：“在正整数范围内，大于1并且只有1和自身两个约数的数”。
什么是素数

int main()
{
    int cont = 0;
    int i = 0;
    //产生100-200之间的数
    for (i = 101; i <= 200; i++)
    {
        //用产生的数  除以比它本身小1的数（从2开始）
        //比如：101  你只能从2开始除到100
        int j = 0;
        int flag = 0; //如果flag=0，那i就是素数，flag是1，i不是素数
        for (j = 2; j < i - 1; j++)
        {
            //试除法 如果i % j == 0 说明j能被i整除，那i就不是素数
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            printf("%d ",i);
            cont++;
        }
    }
    printf("\ncont = %d",cont);
    return 0;
}

优化1：

#include<math.h>
int main()
{
    int cont = 0;
    int i = 0;
    //产生100-200之间的数
    for (i = 101; i <= 200; i++)
    {
        int j = 0;
        int flag = 0; //如果flag=0，那i就是素数，flag是1，i不是素数
        for (j = 2; j <= sqrt(i); j++)
        {
            //试除法 如果i % j == 0 说明j能被i整除，那i就不是素数
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            printf("%d ",i);
            cont++;
        }
    }
    printf("\ncont = %d",cont);
    return 0;
}

优化2：在原来判断数当中减少判断的数量

#include<math.h>
int main()
{
    int cont = 0;
    int i = 0;
    //产生100-200之间的数
    for (i = 101; i <= 200; i+=2)
    {
        int j = 0;
        int flag = 0; //如果flag=0，那i就是素数，flag是1，i不是素数
        for (j = 2; j <= sqrt(i); j++)
        {
            //试除法 如果i % j == 0 说明j能被i整除，那i就不是素数
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            printf("%d ",i);
            cont++;
        }
    }
    printf("\ncont = %d",cont);
    return 0;
}