数论——因子组合【幸运数字】

记录一道关于数论的题目，题目本身不难，主要是学习一下思想~

文章目录

数论——因子组合【幸运数字】
题目
常规思路or错误思路
正确思路（一）
总结

题目

到 X 星球旅行的游客都被发给一个整数，作为游客编号。X 星的国王有个怪癖，他只喜欢数字 3，5 和 7。
国王规定，游客的编号如果只含有因子：3，5，7 就可以获得一份奖品。
我们来看前 10 个幸运数字是：
3 5 7 9 15 21 25 27 35 45 因而第 11 个幸运数字是： 49
小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。
请你帮小明计算一下，59084709587505 是第几个幸运数字。

常规思路or错误思路

首先来分析一下这道题：初次接触此类题的时候，我们通常会想到，先写一个方法——判断某个数的因子是否只含有3，5，7；于是乎，我们写了一个方法，这个方法也确实能够做出准确的判断，而在这个方法中，你或许还会用到一些集合，比如HashSet等…然后输入49，得出是第11个数。

int类型代码如下（Java）：

import java.util.HashSet;

public class Main{
    static HashSet<Integer> hashSet = new HashSet<>();
    public static void main(String[] args) {
//        long num = 59084709587505L;
        int num = 49;
        int count = 2;
        while (3 * count < num) {
            hashSet.add(3 * count);
            count++;
        }
        count = 2;
        while (5 * count < num) {
            hashSet.add(5 * count);
            count++;
        }
        count = 2;
        while (7 * count < num) {
            hashSet.add(7 * count);
            count++;
        }
        count = 0;
        for (int i = 2; i <= num; i++) {
            if (judge(i))
                count++;
        }
        System.out.println(count);
    }

    private static boolean judge(int num) {
        boolean flag = num % 3 == 0 || num % 5 == 0 || num % 7 == 0;
        for (int i = 2; i < num; i++) {
            if (i != 3 && i != 5 && i != 7 && !hashSet.contains(i))
                if (num % i == 0) {
                    flag = false;
                    break;
                }
        }
        return flag;
    }
}

BigInteger类型代码如下（Java）：

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;

public class demo04_BigInteger {
    public static void main(String[] args) {
        BigInteger num = new BigInteger("49");
        int count = 0;
        int i = 2;
        BigInteger temp = new BigInteger(String.valueOf(i));
        while (true) {
            if (temp.compareTo(num) <= 0) {
                if (judge(temp)) {
                    count++;
                    System.out.print(temp+" ");
                }
                temp = new BigInteger(String.valueOf(++i));
            } else break;
        }
        System.out.println(count);
    }


    private static boolean judge2(BigInteger i) {
        if (i.compareTo(BigInteger.valueOf(3)) == 0 || i.compareTo(BigInteger.valueOf(5)) == 0 || i.compareTo(BigInteger.valueOf(7)) == 0)
            return true;
        while (i.mod(BigInteger.valueOf(3)).compareTo(BigInteger.valueOf(0)) == 0)
            i = i.divide(BigInteger.valueOf(3));
        while (i.mod(BigInteger.valueOf(5)).compareTo(BigInteger.valueOf(0)) == 0)
            i = i.divide(BigInteger.valueOf(5));
        while (i.mod(BigInteger.valueOf(7)).compareTo(BigInteger.valueOf(0)) == 0)
            i = i.divide(BigInteger.valueOf(7));
        return i.compareTo(BigInteger.valueOf(1)) == 0;
    }

    private static boolean judge(BigInteger num) {
        boolean flag = Integer.parseInt(num.mod(BigInteger.valueOf(3)).toString()) == 0 || Integer.parseInt(num.mod(BigInteger.valueOf(5)).toString()) == 0 || Integer.parseInt(num.mod(BigInteger.valueOf(7)).toString()) == 0;
        BigInteger temp = new BigInteger(String.valueOf(2));
        while (true) {
            if (temp.compareTo(num) < 0) {
                if (!judge2(temp))
                    if (Integer.parseInt(num.mod(temp).toString()) == 0) {
                        flag = false;
                        break;
                    }
                temp = temp.add(BigInteger.valueOf(1));
            } else
                break;
        }
        return flag;
    }
}

就在我以为大功告成的时候，将数字改为59084709587505（用long存储），发现hashset爆栈了或者是一直跑不出来——超时了！这题这么有难吗？怎么办呢？接着往下看！

正确思路（一）

这里说一下我后来想到的办法，可能还能做优化，但是目前已经是能用的了，如有更好的方法，请在评论区留言指点，不胜感激！

其实这类题和快速幂等数论思想一样，从已知条件入手，不考虑无关内容，从而优化循环，降低复杂度

解题思路：
由于因子只含有3,5,7，所以满足该条件的数一定是由： 3的某次方 * 5的某次方 * 7的某次方构成，而这样组成的数相对于全部的数，它们只占少部分，则可以直接暴力求解！
定义三个变量，三个变量都从0开始，因为一个数的0次方法等于1，相乘不会影响结果，但需要注意的是，要排除掉1这个数字，并且给定的那个数是需要取到的，所以我们列出公式：
for (int x = 0; Math.pow(3, x) <= num; x++)
for (int y = 0; Math.pow(5, y) <= num; y++)
for (int z = 0; Math.pow(7, z) <= num; z++)
这样就能遍历出全部的“幸运数字”，然后加以判断，只要“幸运数字”是<=number的，就追加个数。
代码如下（Java）：

public class Main {

    public static void main(String[] args) {
        long num = 59084709587505L;
        int count = 0;
        for (int x = 0; Math.pow(3, x) <= num; x++)
            for (int y = 0; Math.pow(5, y) <= num; y++)
                for (int z = 0; Math.pow(7, z) <= num; z++)
                    if (Math.pow(3, x) * Math.pow(5, y) * Math.pow(7, z) <= num)
                        count++;

        System.out.println(count - 1);
    }
}