简单数论

First Post:

Last Update:

1 模运算

  • 定义：模运算为 a 除以 m 的余数，记为 a mod m，有 a mod m = a % m。
  • 模运算是大数运算中的常用操作。
  • 如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后，缩小数值再输出。
  • Python 虽然能直接计算大数，不用担心数据溢出，但是大数乘法太耗时，所以也常用取模来缩小数值。
  • 一个简单应用，判断奇偶：a%2=0，a 是偶数；a%2=1，a 是奇数

例题：刷题统计 2022 年第十三届省赛，lanqiaoOJ 题号 2098

【问题描述】 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

【输入格式】 输入一行包含三个整数 a, b 和 n。

【输出格式】 输出一个整数代表天数。

【评测用例规模与约定】 对于 50%的评测用例，1 ≤ a, b, n ≤ 106106；对于 100%的评测用例，1 ≤ a, b, n ≤ 10181018。

题目解析

求余数的简单题，利用求余，把计算复杂度降为 O(1)。

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll a,b,n; cin>>a>>b>>n;
    ll week = a*5+b*2;     //每周做题
    ll days = (n/week)*7;  //周数
    n %= week;             //剩下的做题数
    if(n<=a*5) days += n/a+(n%a?1:0);  //在周一到周五内
    else{                  //周六和周日
        days += 5, n -= a*5;
        days += n/b+(n%b?1:0);
    }
    cout<<days;
    return 0;
}

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), n = sc.nextLong();
        long week = a * 5 + b * 2;  //每周做题
        long days = (n / week) * 7; //周数*7天
        n %= week;                  //余下不够一周的做题数
        if (n <= a * 5)
            days += n / a + (n % a != 0 ? 1 : 0); //在周一到周五内
        else {                       //周六和周日
            days += 5;
            n -= a * 5;
            days += n / b + (n % b != 0 ? 1 : 0);
        }
        System.out.println(days);
        sc.close();
    }
}

Python 代码：

1
2
3
4
5
6
7
8
9
10
11
a, b, n = map(int, input().split())
week = a * 5 + b * 2  #每周做题
days = (n // week) * 7  #天数
n %= week  #余数
if n <= a * 5:
    days += n // a + (n % a != 0)  #在周一到周五内
else:  #周六和周日
    days += 5
    n -= a * 5
    days += n // b + (n % b != 0)
print(days)

2 快速幂

幂运算 an，当 n 很大时，如果一个个乘，时间是 O(n) 的，速度很慢，此时可以用快速幂，在 O(logn) 的时间内算出来。 快速幂的一个解法：分治法，算 a2，然后再算(a2) 2，…，一直算到 an，代码也容易写。

  • 标准的快速幂：用位运算实现。
  • 基于位运算的快速幂，原理是倍增。

快速幂原理

以 a11a11 为例说明如何用倍增法做快速幂。

（1）幂次与二进制的关系。把 a11a11 分解成幂 a8、a2、a1a8、a2、a1 的乘积：a11=a8+2+1=a8×a2×a1a11=a8+2+1=a8×a2×a1。其中a1、a2、a4、a8…a1、a2、a4、a8…的幂次都是 2 的倍数，所有的幂 aiai 都是倍乘关系，逐级递推，代码： a *= a

（2）幂次用二进制分解。如何把 11 分解为 8+2+1？利用数的二进制的特征，n = 1110 = 10112 = 23+21+20 = 8+2+1，把 n 按二进制处理就可以。

（3）如何跳过那些没有的幂次？例如 1011 需要跳过 a4a4。做个判断，用二进制的位运算实现：

  • n & 1 取 n 的最后一位，并且判断这一位是否需要跳过。
  • n >>= 1 把 n 右移一位，目的是把刚处理过的 n 的最后一位去掉。 幂运算的结果往往很大，一般会先取模再输出。 根据取模的性质有：an mod m=(a mod m)n mod manmodm=(amodm)nmodm

例题：快速幂 lanqiaoOJ 题号 1514

【题目描述】给定 b, p, k，求(bp) mod k。其中 2≤b, p, k≤109。 【输入描述】三个整数 b，p，k。 【输出描述】输出(bp) mod k。

题目解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;     //变量改用较大的long long
ll fastPow(ll a, ll n, ll mod){
    ll ans = 1;
    a %= mod;          //重要，防止下面的ans*a越界
    while(n) {
        if(n & 1)   ans = (ans*a) % mod;   //取模
        a = a*a % mod;                     //取模
        n >>= 1;
    }
    return ans;
}
int main(){
    ll b,p,k;    cin>>b>>p>>k;
    cout << fastPow(b,p,k);
    return 0;
}

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main {
    static long fastPow(long a, long n, long mod) {
        long ans = 1;
        a %= mod;   //重要，防止下面的ans*a越界
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = (ans * a) % mod;  //取模
            }
            a = (a * a) % mod;  //取模
            n >>= 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long b = sc.nextLong(), p = sc.nextLong(), k = sc.nextLong();
        System.out.println(fastPow(b, p, k));
        sc.close();
    }
}

Python 代码：

1
2
3
4
5
6
7
8
9
10
11
12
def fast_pow(a, n, mod):
    ans = 1
    a %= mod  #重要，防止下面的ans*a越界
    while n > 0:
        if n & 1 == 1:
            ans = (ans * a) % mod  #取模
        a = (a * a) % mod  #取模
        n >>= 1
    return ans

b, p, k = map(int, input().split())
print(fast_pow(b, p, k))

GCD 定义、性质

最大公约数 Greatest Common Divisor(GCD)：整数 a 和 b 的 GCD 是指能同时整除 a 和 b 的最大整数，记为 gcd(a, b)。由于-a 的因子和 a 的因子相同，因此 gcd(a, b) = gcd(|a|, |b|)。编码时只关注正整数的最大公约数。 性质： （1）gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b) （2）gcd(ka, kb) = k·gcd(a, b) （3）定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。 （4）若 gcd(a, b) = d，则 gcd(a/d, b/d) = 1，即 a/d 与 b/d 互素。这个定理很重要。 （5）gcd(a+cb, b) = gcd(a, b)

C++福利： c++函数 std::__gcd()，可以返回负数，可以带多个参数。

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<__gcd(15, 81)<<"\n";    // 输出  3
    cout<<__gcd(0, 44)<<"\n";     // 输出  44
    cout<<__gcd(0, 0)<<"\n";      // 输出  0
    cout<<__gcd(-6, -15)<<"\n";   // 输出  -3
    cout<<__gcd(-17,289)<<"\n";   // 输出  -17
    cout<<__gcd(17,-289)<<"\n";   // 输出  17
    return 0;
}

手写 GCD 代码

手写 gcd 函数，常用欧几里得算法。 辗转相除法求 gcd： gcd(a, b) = gcd(b, a mod b) 这是最常用的方法，极为高效。 设 a > b，辗转相除法的计算复杂度为O((log2a)3)O((log2a)3)。

可输出负数，和库函数一样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){     return b? gcd(b, a%b):a; }
int main(){
    cout<<gcd(15, 81)<<"\n";    // 输出  3
    cout<<gcd(0, 44)<<"\n";     // 输出  44
    cout<<gcd(0, 0)<<"\n";      // 输出  0
    cout<<gcd(-6, -15)<<"\n";   // 输出  -3
    cout<<gcd(-17,289)<<"\n";   // 输出  -17
    cout<<gcd(17,-289)<<"\n";   // 输出  17
    return 0;
}
// 或者使用如下编码方式：
// int GCD(int a,int b)
// {
//     if(b==0)
//         return a;
//     return GCD(b,a%b);
// }
public class Main {
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(15, 81));   // 输出  3
        System.out.println(gcd(0, 44));    // 输出  44
        System.out.println(gcd(0, 0));     // 输出  0
        System.out.println(gcd(-6, -15));  // 输出  -3
        System.out.println(gcd(-17, 289)); // 输出  17
        System.out.println(gcd(17, -289)); // 输出  17
    }
}
// 或者使用如下编码方式：
// static int GCD(int a,int b)
// {
//     if(b==0)
//         return a;
//     return GCD(b,a%b);
// }
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

print(gcd(15, 81))   # 输出  3
print(gcd(0, 44))    # 输出  44
print(gcd(0, 0))     # 输出  0
print(gcd(-6, -15))  # 输出  -3
print(gcd(-17, 289)) # 输出  17
print(gcd(17, -289)) # 输出  17

# 或者使用如下编码方式：
# def GCD(a,b):

#     if b==0:
#         return a
#     return GCD(b,a%b)

LCM

最小公倍数 LCM (the Least Common Multiple) 。· a 和 b 的最小公倍数 lcm(a,b)(a,b),从算术基本定理推理得到。 算术基本定理：任何大于 1 的正整数 n 都可以唯一分解为有限个素数的乘积：

n=p1c1p2c2…pmcm\rm{n}=\rm{p}_1^{c1}\rm{p}_2^{c2}\ldots\rm{p}m^{cm}n=p1c1p2c2…pmcm,其中c1c1 都是正整数，pi\rm{p}{\rm{i}}pi 都是素数且从小到大。

推导 LCM： 设:a=p1c1p2c2…pmcm,b=p1f1p2f2…pmfm:a=p1c1p2c2…pmcm,b=p1f1p2f2…pmfm

那么：gcd(a, b)=p1min⁡c1,f1p2min⁡c2,f2…pmmin⁡cm,fmb)=p1minc1,f1p2minc2,f2…pmmincm,fm

Icm(a,b)=p1max⁡c1,f1p2max⁡c2,f2…pmmax⁡cm,fm(a,b)=p1maxc1,f1p2maxc2,f2…pmmaxcm,fm

推出：gcd(a, b)lcm(a, b)=ab

即：

lcm(a,b):=:a∗b/gcd(a,b):=:a/gcd(a,:b)∗b.lcm(a,b):=:a∗b/gcd(a,b):=:a/gcd(a,:b)∗b.

lcm()手写代码

1
2
3
4
5
6
7
8
9
10
11
12
13
//c or c++
int lcm(int a, int b){    //需要的时候把int改成long long
   return a / gcd(a, b) * b;  //先做除法再做乘法，防止先做乘法溢出
}

# Python
def lcm(a, b):
    return a // gcd(a, b) * b  #先做除法再做乘法，防止先做乘法溢出

//java
static int lcm(int a, int b) {
    return a / gcd(a, b) * b; //先做除法再做乘法，防止先做乘法溢出
}

核桃的数量 2013 年第四届省赛 lanqiaoOJ 题号 210

【题目描述】小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是： 1.各组的核桃数量必须相同 2.各组内必须能平分核桃（当然是不能打碎的） 3.尽量提供满足 1, 2 条件的最小数量（节约闹革命嘛） 【输入格式】输入三个正整数 a, b, c，表示每个组正在加班的人数，用空格分开（a,b,c< 30）
【输出格式】输出一个正整数，表示每袋核桃的数量。

题目解析

简单题，答案就是三个数字的最小公倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int lcm(int a, int b){ return a / __gcd(a, b) * b;}
int main(){
    int a,b,c;    cin>>a>>b>>c;
    int k = lcm(a,b);
    cout<<lcm(k,c)<<endl;
    return 0;
}
import java.util.Scanner;

public class Main {
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = lcm(a, b);
        System.out.println(lcm(k, c));
        sc.close();
    }
}
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b

a, b, c = map(int, input().split())
k = lcm(a, b)
print(lcm(k, c))

5 素数的判断

素数定义：只能被 1 和自己整除的正整数。注：1 不是素数，最小素数是 2。

判断一个数 n 是不是素数：当n≤1014n≤1014时，用试除法；n > 1014 时，试除法不够用，需 要用高级算法，例如 Miller Rabin 算法。

试除法： 用[2,n-1]内的所有数去试着除 n，如果都不能整除，就是素数。 优化：把[2,n-1]缩小到[2,n][2,n]。证明：若 n = axb, 设 a≤nn ,则 b≥nn,如果 a 是 n 的因子，说明 n 不是素数，b 不用再试且 b 一定也是。

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>

bool is_prime(long long n){
    if(n <= 1)
        return false; // 1不是素数
    for(long long i = 2; i <= sqrt(n); i++)
        if(n % i == 0)
            return false; // 能整除，不是素数
    return true; // 全不能整除，是素数
}

int main() {
    long long number = 29; // 例子：要检查是否为素数的数值
    if (is_prime(number))
        std::cout << number << " 是素数。" << std::endl;
    else
        std::cout << number << " 不是素数。" << std::endl;
    return 0;
}

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main {
    static boolean isPrime(long n) {
        if (n <= 1)
            return false; // 1不是素数
        for (long i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0)
                return false; // 能整除，不是素数
        return true; // 全不能整除，是素数
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("输入一个要检查是否为素数的数值：");
        long number = scanner.nextLong(); // 例子：要检查是否为素数的数值

        if (isPrime(number))
            System.out.println(number + " 是素数。");
        else
            System.out.println(number + " 不是素数。");
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
def is_prime(n):
    if n <= 1:
        return False  # 1不是素数
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False  # 能整除，不是素数
    return True  # 全不能整除，是素数

number = 29  # 例子：要检查是否为素数的数值
if is_prime(number):
    print(number, "是素数。")
else:
    print(number, "不是素数。")

6 素数筛

素数的筛选：给定 n，求 2~n 内所有的素数。 一个个地判断很慢，所以用“筛子”筛所有的整数，把非素数筛掉，剩下的就是素数。 常用两种筛法：埃氏筛、欧拉筛。

埃氏筛:

初始队列{2、3，4，5，6，7，8，9，10，11，12，13，…，n}，操作步骤： （1）输出最小的素数 2，筛掉 2 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…} （2）输出最小的素数 3，筛掉 3 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…} （3）输出最小的素数 5，筛掉 5 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…} 继续以上步骤，直到队列为空。

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int primes[N],cnt;
bool bprime[N];
void getPrime(int n){
    memset(bprime,false,sizeof(bprime));
    bprime[0]=true;
    bprime[1]=true;

    for(int i=2;i<=n;i++){
        if(!bprime[i]){
            prime[cnt++]=i;
            for(LL j=i*2;j<=n;j+=i)
                bprime[j]=true;
        }
    }
}

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] primes = new int[N];
int cnt;
boolean[] bprime = new boolean[N];

void getPrimes(int n) {
    Arrays.fill(bprime, false);
    bprime[0] = true;
    bprime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (!bprime[i]) {
            primes[cnt++] = i;
            for (int j = i * 2; j <= n; j += i) {
                bprime[j] = true;
            }
        }
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
primes = [0] * N
cnt = 0
bprime = [False] * N

def getPrimes(n):
    global cnt, primes, bprime
    bprime[0] = True
    bprime[1] = True
    for i in range(2, n+1):
        if not bprime[i]:
            primes[cnt] = i
            cnt += 1
            for j in range(i*2, n+1, i):
                bprime[j] = True

但是埃氏筛法的缺点：例如 6 会被 3 整除，6 会被 2 整除，会被筛两次，所以我们再给出欧氏线性筛法：

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N],cnt;
bool bPrime[N];
void getPrimes(int n){
    memset(bPrime,false,sizeof(bPrime));

    for(int i=2;i<=n;i++){
        if(!bPrime[i])
            primes[cnt++]=i;

        for(int j=0;j<cnt&&i*primes[j]<n;j++){
            bPrime[i*primes[j]]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int[] primes = new int[N], bPrime = new int[N];
static int cnt;

public static void getPrimes(int n) {
    Arrays.fill(bPrime, 0, n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (bPrime[i] == 0)
            primes[cnt++] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            bPrime[i * primes[j]] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = 1000005
primes = [0] * N
bprime = [False] * N
cnt = 0

def getPrimes(n: int):
    global cnt
    for i in range(2, n+1):
        if not bprime[i]:
            primes[cnt] = i
            cnt += 1
        j = 0
        while j < cnt and i * primes[j] <= n:
            bprime[i * primes[j]] = True
            if i % primes[j] == 0:
                break
            j += 1

例题：质数 lanqiaoOJ 题号 1557

【题目描述】给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。 【输入描述】一个正整数 N，n<1000 【输出描述】两行，第 1 行包含若干个素数，从小到大输出，用空格分开。第 2 行一个整数，表示素数个数。

输入： 10

输出： 2 3 5 7 4

题目为模板题目，实现方式如下，其中：

  • bprime[i]记录数 i 的状态，若 bprime [i]=1，表示它被筛掉，不是素数。
  • 用 primes[]存放素数，prime[0]是第一个素数 2。
  • Cnt 是素数个数计数

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int primes[N],cnt;
bool bprime[N]; //true表示被筛掉，不是素数
void getPrimes(int n){ //埃氏筛，计算[2, n]内的素数
        memset(bprime,false,sizeof(bprime));
        bprime[0]=true;
        bprime[1]=true;

        for(int i=2;i<=n;i++){
            if(!bprime[i]){
                primes[cnt++]=i;
                for(int j=i*2;j<=n;j+=i)
                    bprime[j]=true;
            }
        }
    }

int main(){
    int n;
    cin >>n;
    getPrimes(n-1);
    for(int i=0;i<cnt;i++)  cout << primes[i]<<" ";
    cout << endl;
    cout << cnt;
}

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Main {
    static final int N = 1000000;
    static int[] primes = new int[N];
    static boolean[] bprime = new boolean[N];
    static int cnt;

    public static void getPrimes(int n) {
        bprime[0] = true;
        bprime[1] = true;

        for (int i = 2; i <= n; i++) {
            if (!bprime[i]) {
                primes[cnt++] = i;
                for (int j = i * 2; j <= n; j += i) {
                    bprime[j] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        getPrimes(n - 1);
        for (int i = 0; i < cnt; i++) {
            System.out.print(primes[i] + " ");
        }
        System.out.println();
        System.out.println(cnt);
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
N = 10**6
primes = []
bprime = [False] * N

def getPrimes(n):
    global primes
    global cnt

    bprime[0] = True
    bprime[1] = True

    for i in range(2, n+1):
        if not bprime[i]:
            primes.append(i)
            cnt += 1
            for j in range(i*2, n+1, i):
                bprime[j] = True

n = int(input())
cnt = 0
getPrimes(n-1)

for p in primes:
    print(p, end=' ')
print()

print(cnt)

7 分解质因子

任何一个正整数 n 都可以唯一地分解为有限个素数的乘积：n=p1c1p2c2…pmcmn=p1c1p2c2…pmcm,其中cici都是正整数，p*i 都是素数且从小到大。 分解质因子也可以用试除法。求 n 的质因子：

  1. 第一步，求最小质因子p1p1。逐个检查从2到 nn 的所有素数，如果它能整除 n，就是最小质因子。然后连续用 p1p1除 n，目的是去掉 n 中的 p1p1,得到 n1n1。
  2. 第二步，再找 n1n1的最小质因子。逐个检查从 p1p1 到 n1n1 的所有素数。从 p1p1开始试除， 是因为 n1n1没有比 p1p1小的素因子，而且 n1n1的因子也是 n 的因子。
  3. 继续以上步骤，直到找到所有质因子。

我们直接看一个例题：

【题目描述】求出区间[a,b]中所有整数的质因数分解。 【输入描述】输入一行，包含 2 个整数 a，b。2<=a<=b<=10000 【输出描述】每行输出一个数的分解，形如 k=a1×a2×a3×…，k 从小到大，a 从小到大。

输入： 3 10

输出： 3=34=2×25=56=2×37=78=2×2×29=3×310=2×5\begin{aligned} &\text{3=} \text{3} \ &\text{4=} 2\times2 \ &\text{5=} \text{5} \ &6=2\times3 \ &\text{7=7} \ &8=2\times2\times2 \ &9=3\times3 \ &10=2\times5 \end{aligned}3=34=2×25=56=2×37=78=2×2×29=3×310=2×5

直接对每个数进行分解，然后打印出它的因数。

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int p[20];  //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40];  //c[i]记录第i个因子的个数。一个因子的个数最多有30几个
int factor(int n){
    int m = 0;
    for(int i = 2; i <= sqrt(n); i++)
        if(n%i == 0){
            p[++m] = i, c[m] = 0;
            while(n%i == 0)            //把n中重复的因子去掉
                n/=i, c[m]++;
        }
    if(n>1)                           //没有被除尽，是素数
        p[++m] = n, c[m] = 1;
    return m;                         //共m个因子
}
int main(){
    int a,b;   cin>>a>>b;
    for(int i=a;i<=b;i++){
        int m = factor(i);
        cout<<i<<"=";
        for(int j=1;j<=m;j++){ //第j个因子
            for(int k=1;k<=c[j];k++){    //第j个因子的个数
                cout <<p[j];
                if(k<c[j]) cout <<"*";
            }
            if(j<m) cout <<"*";
        }
        cout<<endl;
    }
    return 0;
}

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;

public class Main {
    static int[] p = new int[20];  // p[] 记录因子，p[1] 是最小因子。一个 int 数的质因子最多有 10 几个
    static int[] c = new int[40];  // c[i] 记录第 i 个因子的个数。一个因子的个数最多有 30 几个

    static int factor(int n) {
        int m = 0;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                p[++m] = i;
                c[m] = 0;
                while (n % i == 0) {
                    n /= i;
                    c[m]++;
                }
            }
        }
        if (n > 1) {
            p[++m] = n;
            c[m] = 1;
        }
        return m;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        for (int i = a; i <= b; i++) {
            int m = factor(i);
            System.out.print(i + "=");
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= c[j]; k++) {
                    System.out.print(p[j]);
                    if (k < c[j]) {
                        System.out.print("*");
                    }
                }
                if (j < m) {
                    System.out.print("*");
                }
            }
            System.out.println();
        }
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import math

p = [0] * 20  # p[] 记录因子，p[1] 是最小因子。一个 int 数的质因子最多有 10 几个
c = [0] * 40  # c[i] 记录第 i 个因子的个数。一个因子的个数最多有 30 几个

def factor(n):
    m = 0
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            m += 1
            p[m], c[m] = i, 0
            while n % i == 0:
                n //= i
                c[m] += 1
    if n > 1:
        m += 1
        p[m], c[m] = n, 1
    return m

a, b = map(int, input().split())
for i in range(a, b+1):
    m = factor(i)
    print(f'{i}=', end='')
    for j in range(1, m+1):
        for k in range(1, c[j]+1):
            print(p[j], end='')
            if k < c[j]:
                print('*', end='')
        if j < m:
            print('*', end='')
    print()

15 届蓝桥杯 14 天省赛冲刺营 1 期 - 简单数论 - 蓝桥云课 (lanqiao.cn)

≡