java实现整数分解几个质数的积并统计3出现的次数

上一篇文章已经实现了一个整数分解为两个质数乘积，但针对这张图片，还有一个附加题，统计3出现的次数。下面我们来看下思路：

最优思路：从数字规律着手，提高时间效率

• 如果第i位（从低位向高位开始）上的数字是0，那么第i位可能出现1的次数仅由更高位决定（如果没有高位，则视高位为0），等于更高位数字*当前位数的权重10^(i-1)；
• 如果第i位上的数字为1，则第i位上可能出现1的次数不仅受更高位影响还受低位影响（如果没有低位，则视低位为0），等于更高位数字*当前位数的权重10^(i-1) + (低位数字+1)；
• 如果第i位上的数字大于1，则第i位上可能出现1的次数仅由更高位决定（如果没有高位，则视高位为0），等于（更高位数字+1）*当前位数的权重10^(i-1)。

注：（这里的 X∈[1,9] ，因为 X=0 不符合下列规律，需要单独计算）。

首先要知道以下的规律：

从 1 至 10，在它们的个位数中，任意的 X 都出现了 1 次。

从 1 至 100，在它们的十位数中，任意的 X 都出现了 10 次。

从 1 至 1000，在它们的百位数中，任意的 X 都出现了 100 次。

依此类推，从 1 至 10^ i ，在它们的左数第二位（右数第 i 位）中，任意的 X 都出现了 10^(i-1) 次。

以21354为例，寻找1出现的次数：

个位：从1至21350中包含了2135个10，因此1出现了2135次，21351，21352，21353，21354其中21351包含了一个1，故个位出现1的次数为：2135*10(1-1) + 1 = 2136次；

公式：( 2135+1）* 10^(1-1) = 2136；

十位：从1到21300中包含了213个100，因此1出现了213 * 10^(2-1) = 2130次，剩下的数字是21301到21354，它们的十位数字是5 > 1；因此它会包含10个1；故总数为2130 + 10 = 2140次；

公式：（213 + 1）* 10^(2-1) = 2140次；

百位：从1到21000中包含了21个1000，因此1出现了21 * 10^(3-1) = 2100次，剩下的数字是21001到21354，它们的百位数字是3 > 1；因此它会包含100个1；故总数为2100 + 100 = 2200次；

公式：（21 + 1）* 10^(3-1) = 2200次；

千位：从1到20000中包含了2个10000，因此1出现了2 * 10^(4-1) = 2000次，剩下的数字是20001到21354，它们的千位数字是1 = 1；情况稍微复杂些，354 + 1 = 355；故1的总数为2000 + 355 = 2355次；

公式：2 * 10^(4-1) + 354 + 1 = 2355次；

万位：万位是2 > 1，没有更高位；因此1出现的次数是1 * 10^(5-1) = 10000次；

公式：（0 + 1）*10^(5-1) = 10000次；

故总共为：2136+2140+2200+2355+10000=18831次；

故总结：

1、取第 i 位左边的数字（高位），乘以 10 ^(i−1) ，得到基础值 a 。
2、取第 i 位数字，计算修正值：

• 如果大于 X，则结果为 a+ 10 ^(i−1) 。
• 如果小于 X，则结果为 a 。
• 如果等 X，则取第 i 位右边（低位）数字，设为 b ，最后结果为 a+b+1 。

代码实现：

package com.test;

import java.util.Scanner;

/**
 * @author riemann
 * @date 2019/04/12 20:35
 */
public class TestPrimeNumber {
    public static void main(String[] args) {
        System.out.println("请输入了一个大于2的整数:");
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();//707829217
        int x = 3;//所有数里出现3
        primeCount(input);//707829217
        long start = System.currentTimeMillis();
        System.out.println("3总共出现了: " + occurrencesCount(input,x) + "次");
        long end = System.currentTimeMillis();
        System.out.println("执行共耗时: " + (end - start) + "ms");
    }

    private static void primeCount(int num) {
        StringBuilder sb = new StringBuilder();
        sb.append(num + "=");
        int minPrimeNumber = 2;// 定义最小的质数
        while (minPrimeNumber < num) {
            if (num % minPrimeNumber == 0) {
                num = num / minPrimeNumber;
                sb.append(minPrimeNumber + "*");
            } else {
                minPrimeNumber++;
            }
        }
        sb.append(minPrimeNumber);
        System.out.println(sb.toString());
    }

    private static int occurrencesCount(int n, int x) {
        if (n < 0 || x < 1 || x > 9) {
            return 0;
        }
        int low, cur, high = n, temp, i = 1, total = 0;
        while (high != 0) {
            high = (int) (n / Math.pow(10, i));             //获取第i位的高位
            temp = (int) (n % Math.pow(10, i));
            cur = (int) (temp / Math.pow(10, i - 1));       //获取第i位
            low = (int) (temp % Math.pow(10, i - 1));       //获取第i位的低位
            if (cur == x) {
                total += high * Math.pow(10, i - 1) + low + 1;
            } else if (cur < x) {
                total += high*(int) Math.pow(10, i-1);
            } else {//大于x
                total += (high + 1) * (int)Math.pow(10, i-1);
            }
            i++;
        }
        return total;
    }
}

output：