最大质因子序列

任意输入两个正整数m, n (1 < m < n <= 5000)，依次输出m到n之间每个数的最大质因子（包括m和n；如果某个数本身是质数，则输出这个数自身）。

输入

一行，包含两个正整数m和n，其间以单个空格间隔。

输出

一行，每个整数的最大质因子，以逗号间隔。

样例输入

5 10

样例输出

5,3,7,2,3,5

C语言代码

#include <stdio.h>
#include <stdbool.h>

// 判断一个数是否为质数
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) { // 从2到根号num判断能否整除
        if (num % i == 0) return false;
    }
    return true;
}

// 求一个数的最大质因子
int maxPrimeFactor(int num) {
    int maxFactor = num;
    for (int i = 2; i * i <= num; i++) { // 从2到根号num尝试分解
        while (num % i == 0) {
            maxFactor = i;
            num /= i;
        }
    }
    if (num > 1) { // 如果最后剩下的数大于1，那它就是最大质因子（本身是质数情况）
        maxFactor = num;
    }
    return maxFactor;
}

int main() {
    int m, n;
    scanf(“%d %d”, &m, &n);
    for (int i = m; i <= n; i++) { // 遍历m到n的每个数
        int factor = maxPrimeFactor(i);
        if (i!= m) printf(“,”); // 除了第一个数，其余数前输出逗号
        printf(“%d”, factor);
    }
    printf(“\n”);
    return 0;
}

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;

// 判断一个数是否为质数
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++) { // 从2到根号num判断能否整除
        if (num % i == 0) return false;
    }
    return true;
}

// 求一个数的最大质因子
int maxPrimeFactor(int num) {
    int maxFactor = num;
    for (int i = 2; i <= sqrt(num); i++) { // 从2到根号num尝试分解
        while (num % i == 0) {
            maxFactor = i;
            num /= i;
        }
    }
    if (num > 1) { // 如果最后剩下的数大于1，那它就是最大质因子（本身是质数情况）
        maxFactor = num;
    }
    return maxFactor;
}

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = m; i <= n; i++) { // 遍历m到n的每个数
        int factor = maxPrimeFactor(i);
        if (i!= m) cout << “,”; // 除了第一个数，其余数前输出逗号
        cout << factor;
    }
    cout << endl;
    return 0;
}

Java代码

import java.util.Scanner;

public class MaxPrimeFactorRange {
     // 判断一个数是否为质数
    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) { // 从2到根号num判断能否整除
            if (num % i == 0) return false;
        }
        return true;
    }

     // 求一个数的最大质因子
    static int maxPrimeFactor(int num) {
        int maxFactor = num;
        for (int i = 2; i * i <= num; i++) { // 从2到根号num尝试分解
            while (num % i == 0) {
                maxFactor = i;
                num /= i;
            }
        }
        if (num > 1) { // 如果最后剩下的数大于1，那它就是最大质因子（本身是质数情况）
            maxFactor = num;
        }
        return maxFactor;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        for (int i = m; i <= n; i++) { // 遍历m到n的每个数
            int factor = maxPrimeFactor(i);
            if (i!= m) System.out.print(“,”); // 除了第一个数，其余数前输出逗号
            System.out.print(factor);
        }
        System.out.println();
    }
}

Python代码

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1): // 从2到根号num判断能否整除
        if num % i == 0:
            return False
    return True

def max_prime_factor(num):
    factor = num
    for i in range(2, int(num ** 0.5) + 1): // 从2到根号num尝试分解
        while num % i == 0:
            factor = i
            num //= i
    if num > 1: // 如果最后剩下的数大于1，那它就是最大质因子（本身是质数情况）
        factor = num
    return factor

m, n = map(int, input().split())
result = []
for i in range(m, n + 1): // 遍历m到n的每个数
    result.append(max_prime_factor(i))
print(“,”.join(map(str, result)))