【分解质因数】数数【蓝桥杯】

题目

数数 - 蓝桥云课

---

问题描述

任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 $28=2 \times 2 \times 7$ 被分解为了三个质数相乘。请问在区间 $[2333333, 23333333]$ 中有多少个正整数可以被分解为 12 个质数相乘?

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题

方法一：枚举 分解质因数

思路

填空题就直接暴力做了，枚举 $2333333 \dots 23333333$ ，对每一个数分解质因数、计数并判断。

代码

import java.util.*;
import java.io.*;

public class _数数 {
    static boolean check(int n) {
        int cnt = 0;
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                    ++cnt;
                }
                if (cnt > 12) return false;
            }
        }
        if (n > 1) ++cnt;
        return cnt == 12;
    }

    public static void main(String[] args) {
        int cnt = 0;
        for (int i = 2333333; i <= 23333333; ++i) {
            if (check(i)) ++cnt;
        }
        System.out.println(cnt);
    }
}

// 大概算了35s左右 是可以跑出来的
// public class Main {
//     public static void main(String[] args) {
//         System.out.println(25606);
//     }
// }