侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-14 / 0 评论 / 0 点赞 / 17 阅读 / 336 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

数数 - 蓝桥云课


问题描述

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

答案提交

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

运行限制

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

解题

方法一:枚举 分解质因数

思路

填空题就直接暴力做了,枚举 2333333233333332333333 \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);
//     }
// }
0

评论区