数论——因子组合【幸运数字】
记录一道关于数论的题目，题目本身不难，主要是学习一下思想~
题目
到 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); } }
总结
当我们初次接触到这类问题时，总是以最直观的方法进行求解，却没有想到耗时问题；应该仔细分析已知条件，从已知的条件入手能够排除掉很多无关的数字，从而大大降低时间空间开销！
文章粗浅，希望对大家有帮助！
