最大公约数和最小公倍数

#include <iostream>
#include <string>
#include <algorithm>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;
//欧几里得算法（辗转相除法）
//求a,b最大公因数
//设a=kb+r
//则有r=a-kb成立
//设d为a和b的一个公约数
//那么由r=a-kb,d也是r的一个约数
//又有r=a%b，d是b和a%b的一个公约数
//由d的任意性，得a,b的公约数都是b和a%b的公约数
//由a=kb+r，同理可证b和a%b的公约数都是a,b的公约数和
//由此a和b的公约数与b和a%b的公约数全部相等，故其最大公约数也相等
//即有gcd(a,b)=gcd(b,a%b)
int gcd(int a, int b) {//a>b
    if (b == 0)return a;//递归边界，0和任意一个整数（非0）的最大公约数都是a
    else return gcd(b, a % b);
}
 
//最小公倍数是ab/d
int lcm(int a, int b) {//a>b
    return a * b / gcd(a, b);
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a < b) {
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    cout << "最大公因数：" << gcd(a, b) << endl;
    cout << "最小公倍数：" << lcm(a, b) << endl;
}

素数

#include <iostream>
#include <string>
#include <algorithm>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;

//素数判定
bool isPrime(int n) {
    if (n <= 1)return false;
    for (int i = 2; i <= (int)sqrt(1.0 * n); i++) {
        if (n % i == 0)return false;
    }
    return true;
}

//素数表获取
const int maxn_1 = 101;//表长
int prime_1[maxn_1];//存放素数
int pnum_1 = 0;//素数个数
bool p_1[maxn_1] = { 0 };//p[i]==true,表示i是素数

void get_prime() {
    for (int i = 1; i < maxn_1; i++) {
        if (isPrime(i) == true) {
            prime_1[pnum_1] = i;
            pnum_1++;
            p_1[i] = true;
        }
    }
}

void prime_table() {
    get_prime();
    cout << "素数表：";
    for (int i = 0; i < pnum_1; i++) {
        cout << prime_1[i] << ' ';
    }
}

//素数筛法
//对于每一个素数，筛去它的所有倍数
const int maxn_2 = 101;//表长
int prime_2[maxn_2];//存放素数
int pnum_2 = 0;//素数个数
bool p_2[maxn_2] = {1};//p[i]==true,表示i是素数

void sieve_prime() {
    fill(p_2, p_2 + maxn_2, true);
    for (int i = 2; i < maxn_2; i++) {
        if (p_2[i] == true) {//如果i是素数
            prime_2[pnum_2] = i;
            pnum_2++;
            for (int j = i + i; j < maxn_2; j += i) {
                p_2[j] = false;
            }
        }
    }
}

void sieve_prime_table() {
    sieve_prime();
    cout << "素数筛法：";
    for (int i = 0; i < pnum_2; i++) {
        cout << prime_2[i] << ' ';
    }
}

int main() {
    prime_table();
    cout << endl;
    sieve_prime_table();
}