数学题目系列(一)|丑数|各位和|埃氏筛|欧拉筛

一.丑数

链接：丑数

分析：

• 丑数只有2，3，5这三个质因数，num = 2^a + 3^b + 5^c
• 也就是一个丑数是由若干个2，3，5组成，那么丑数除以这若干个数字最后一定变为1

代码

class Solution {public boolean isUgly(int n) {if (n <= 0) return false;int[] factors = { 2, 3, 5 };for (int factor : factors)while (n % factor == 0)n /= factor;return n == 1;}
}

二.丑数II

链接：丑数II

分析

• 最容易想到的思路是暴力解法，因为在上一题中已经知道判断一个丑数的方法，但是时间复杂度太高，不能通过所有样例

暴力解法(无法通过所有样例)

class Solution {private boolean isUgly(int n) {int[] factors = {2,3,5};for(int factor : factors)while(n % factor == 0)n /= factor;return n == 1;}public int nthUglyNumber(int n) {int ret = 0, cnt = 0;for(int i = 1;;i++) {if(isUgly(i)) cnt++;if(cnt == n) return i;}}
}

• 要取出第n大的丑数，可以使用优先级队列来存储丑数，丑数非常容易获得，就是由前一个丑数分别乘2,3,5所得
• 首先创建最小堆，堆顶元素为最小的丑数
• 初始化最小堆，堆顶元素为最小的丑数1
• 取出堆顶元素x，第几次取出就是第几大的丑数
• x是丑数，那么2x，3x，5x也都是丑数，将这三个数存储到优先级队列之中
• 在这个过程中可能会出现重复元素，可以使用哈希表来去重
• 这样，当第n次取出堆顶元素x时，x就是第n大的丑数

代码

class Solution {public int nthUglyNumber(int n) {int[] factors = {2, 3, 5};Set<Long> set = new HashSet<>();PriorityQueue<Long> q = new PriorityQueue<>();set.add(1L);q.add(1L);for(int i = 1; i < n; i++) {long top = q.poll();for(int factor : factors){long next = top * factor;if(set.add(next))q.add(next); }}return (int)q.poll().longValue();}
}

注意：

1. 注意Long和long是不同的，Long是包装类，long是基本类型
2. Java中，基本类型之间可以直接进行强制类型转换(int x = (int)long)
3. 基本类型和其对应的包装类型在底层是通过方法进行转换的，但是在JDK5之后，编译器会自动帮助我们完成这个过程，也就是拆箱和装箱
4. 包装类不能直接转换为另一个包装类或原始数据类型，必须先进行拆箱或装箱
5. Long 不能直接转换为 int，因为它们是不同的类型，必须先将 Long 拆箱为 long，然后再转换为 int。
6. Long转化为long是通过longvalue方法实现

三.各位相加

链接：各位相加

分析

• 模拟思路：不断获得每一位，然后计算各位和，直到最后的结果是个位数

代码

class Solution {// 求各位和private int bitSum(int n) {int ret = 0;while (n > 0) {ret += n % 10;n /= 10;}return ret;}public int addDigits(int num) {int ret = num;while(ret / 10 != 0) {ret = bitSum(ret);}return ret;}
}

数学方法
看推导：

• 核心在于：num和其各位和 MOD9同余
• 进而推导出num和最后的结果MOD9同余

代码

class Solution {public int addDigits(int num) {if(num == 0) return 0;if(num % 9 == 0) return 9;return num % 9;}
}

四.计数质数

暴力解法(超时)

class Solution {private boolean isPrime(int n) {for(int i = 2; i <= Math.sqrt(n); i++){if(n % i == 0)return false;}return true;}public int countPrimes(int n) {int cnt = 0;for(int i = 2; i < n; i++)if(isPrime(i))cnt++;return cnt;}
}

埃氏筛

• 核心：如果x是质数，则2x,3x,4x,5x…一定不是质数
• 利用这个原理就能灵活处理很多问题

代码

class Solution {public int countPrimes(int n) {int[] is_prime = new int[n];// 标记第i个数是否是质数Arrays.fill(is_prime,1);// 默认全是质数int ret = 0;// 记录结果for(int i = 2; i < n; i++) {if(is_prime[i] == 1) {ret += 1;if((long)i*i < n)for(int k = i * i; k < n; k += i)is_prime[k] = 0;}}return ret;}
}

线性筛

• 埃氏筛其实还存在冗余的地方，比如12这个数字，被2，4，6都删除过一次，这就是冗余操作，使用线性筛可以解决这个问题
• 线性筛的核心在于：对于一个数x，x乘以小于x的所有质数的结果一定是合数，将这些结果标记为非质数即可，但是发现这样的删除过程仍然存在冗余操作，问题及解决方案如下

代码：

class Solution {public int countPrimes(int n) {List<Integer> list = new ArrayList<>();// 存储之前出现的所有质数int[] is_prime = new int[n];Arrays.fill(is_prime,1);int ret = 0;for(int i = 2; i < n; i++) {if(is_prime[i] == 1){list.add(i);ret++;}for(int k : list){if(k*i >= n) break;is_prime[k*i] = 0;if(i % k == 0) break;// k是i的最小质因数}}return ret;}
}

三种算法的时间复杂度对比(数据量大)

• 线性筛 > 埃氏筛 > 暴力解法

对比实验：求2-n之间所有的质数
代码：

package org.example;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;// 打印2-n之间的所有质数
public class Demo2 {// 埃氏筛public static void Eratosthenes(int n) {List<Integer> list = new ArrayList<>();int[] is_prime = new int[n + 1];Arrays.fill(is_prime, 1);for(int i = 2; i <= n; i++) {if(is_prime[i] == 1){list.add(i);if((long)i*i <= n)for(int k = i*i; k <= n; k += i)is_prime[k] = 0;}}}// 暴力解法public static void isPrime(int n){List<Integer> list = new ArrayList<>();for(int i = 2; i<= n; i++){if(is_prime(i))list.add(i);}}private static boolean is_prime(int n){for(int i = 2; i <= Math.sqrt(n); i++)if(n % i == 0)return false;return true;}// 线性筛public static void Euler_prime(int n){List<Integer> list = new ArrayList<>();int[] is_prime = new int[n + 1];Arrays.fill(is_prime, 1);for(int i = 2; i <= n; i++) {if(is_prime[i] == 1)list.add(i);for(int k : list){if(k*i > n) break;is_prime[k*i] = 0;if(i % k == 0) break;// k是i的最小质因数}}}public static void main(String[] args) {int n = 200000000;long start1 = System.currentTimeMillis();Eratosthenes(n);long end1 = System.currentTimeMillis();System.out.println("埃氏筛时间:" + (end1 - start1));long start2 = System.currentTimeMillis();isPrime(n);long end2 = System.currentTimeMillis();System.out.println("暴力时间:" + (end2 - start2));long start3 = System.currentTimeMillis();Euler_prime(n);long end3 = System.currentTimeMillis();System.out.println("线性筛时间:" + (end3 - start3));}
}

打印结果：

• 只有当数据量特别大时，才符合上述时间复杂度的排序，对于计算机来说，取模%是一个非常耗时的操作