【NOIP普及组】质因数分解

- - C语言代码
  - C++代码
  - Java代码
  - Python代码

💐The Begin💐点点关注，收藏不迷路💐

已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。

输入

输入只有一行，包含一个正整数 n。

输出

输出只有一行，包含一个正整数 p，即较大的那个质数。

样例输入

样例输出

提示

【数据范围】
对于 60%的数据，
6≤n≤1000。
对于 100%的数据，
6≤n≤2∗10^9 。

C语言代码

#include <stdio.h>
#include <math.h>

int main() {
    int n;  // 存储输入的正整数
    scanf("%d", &n);  // 读取输入的正整数

    int maxPrime = 0;  // 用于存储较大的质数，初始化为0

    // 从2开始遍历到n的平方根，因为一个数的因数不会超过它的平方根
    for (int i = 2; i <= sqrt(n); i++) { 
        if (n % i == 0) {  // 如果i是n的因数
            int otherFactor = n / i;  // 计算另一个因数

            // 判断i和另一个因数是否都是质数
            int isIprime = 1;
            for (int j = 2; j <= sqrt(i); j++) {
                if (i % j == 0) {
                    isIprime = 0;
                    break;
                }
            }

            int isOtherFactorPrime = 1;
            for (int j = 2; j <= sqrt(otherFactor); j++) {
                if (otherFactor % j == 0) {
                    isOtherFactorPrime = 0;
                    break;
                }
            }

            // 如果i和另一个因数都是质数，更新较大的质数
            if (isIprime && isOtherFactorPrime) {
                maxPrime = (i > otherFactor)? i : otherFactor;
            }
        }
    }

    printf("%d\n", maxPrime);  // 输出较大的质数

    return 0;
}

C++代码

#include <iostream>
#include <cmath>

int main() {
    int n;  // 存储输入的正整数
    std::cin >> n;  // 读取输入的正整数

    int maxPrime = 0;  // 用于存储较大的质数，初始化为0

    // 从2开始遍历到n的平方根，因为一个数的因数不会超过它的平方根
    for (int i = 2; i <= std::sqrt(n); i++) { 
        if (n % i == 0) {  // 如果i是n的因数
            int otherFactor = n / i;  // 计算另一个因数

            // 判断i和另一个因数是否都是质数
            bool isIprime = true;
            for (int j = 2; j <= std::sqrt(i); j++) {
                if (i % j == 0) {
                    isIprime = false;
                    break;
                }
            }

            bool isOtherFactorPrime = true;
            for (int j = 2; j <= std::sqrt(otherFactor); j++) {
                if (otherFactor % j == 0) {
                    isOtherFactorPrime = false;
                    break;
                }
            }

            // 如果i和另一个因数都是质数，更新较大的质数
            if (isIprime && isOtherFactorPrime) {
                maxPrime = (i > otherFactor)? i : otherFactor;
            }
        }
    }

    std::cout << maxPrime << std::endl;  // 输出较大的质数

    return 0;
}

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取输入的正整数

        int maxPrime = 0;  // 用于存储较大的质数，初始化为0

        // 从2开始遍历到n的平方根，因为一个数的因数不会超过它的平方根
        for (int i = 2; i <= Math.sqrt(n); i++) { 
            if (n % i == 0) {  // 如果i是n的因数
                int otherFactor = n / i;  // 计算另一个因数

                // 判断i和另一个因数是否都是质数
                boolean isIprime = true;
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        isIprime = false;
                        break;
                    }
                }

                boolean isOtherFactorPrime = true;
                for (int j = 2; j <= Math.sqrt(otherFactor); j++) {
                    if (otherFactor % j == 0) {
                        isOtherFactorPrime = false;
                        break;
                    }
                }

                // 如果i和另一个因数都是质数，更新较大的质数
                if (isIprime && isOtherFactorPrime) {
                    maxPrime = (i > otherFactor)? i : otherFactor;
                }
            }
        }

        System.out.println(maxPrime);  // 输出较大的质数

        scanner.close();
    }
}

Python代码

import math

n = int(input())  # 读取输入的正整数

maxPrime = 0  # 用于存储较大的质数，初始化为0

# 从2开始遍历到n的平方根，因为一个数的因数不会超过它的平方根
for i in range(2, int(math.sqrt(n)) + 1): 
    if n % i == 0:  # 如果i是n的因数
        otherFactor = n // i  # 计算另一个因数

        # 判断i和另一个因数是否都是质数
        isIprime = all(i % j!= 0 for j in range(2, int(math.sqrt(i)) + 1))
        isOtherFactorPrime = all(otherFactor % j!= 0 for j in range(2, int(math.sqrt(otherFactor)) + 1))

        # 如果i和另一个因数都是质数，更新较大的质数
        if isIprime and isOtherFactorPrime:
            maxPrime = max(i, otherFactor)

print(maxPrime)  # 输出较大的质数