【小航的算法日记】素数判定

【小航的算法日记】素数判定

目录

一、概念二、模板三、例题

题：866. 回文素数解：题：剑指 Offer 49. 丑数解：
具体内容请看英雄哥解释，以下是Java版

一、概念

性质：

任意性传递性可消性组合型

二、模板

素数判定模板：

boolean isPrime(int n) {
        if(n <= 1) return false;
        if(n == 2) return true;   // 一定要先写2是素数
        if((n & 1) == 0) return false; // 然后再写偶数不是素数     
        for(int i = 3; i * i <= n; i += 2) {
            if(n % i == 0) return false;
        }
        return true;
    }

回文数判定模板：

boolean isPal(int n) {
        if(n < 0 || (n % 10 == 0 && n != 0)) return false;
        int reverN = 0; // 将n与反转后reverN进行比对
        while(n > reverN) {
            reverN = reverN * 10 + n % 10;
            n = n / 10;
        }
        return n == reverN || n == reverN / 10; // 奇偶长度情况
    }

计算数字位数模板：

int numlen(int n) {
        n = Math.abs(n);
        if(n < 10) return 1;
        else return numlen(n / 10) + 1;
    }

根据回文数推下一个回文数：

int nextPal(int n) {
        int len = numlen(n);
        int p = (int)(Math.pow(10, len / 2));
        int left = n / p + 1; // 得到左边一半 + 1；
        // 计算右一半
        int right = 0; int temp = left;
        while(temp > 0) {
            right = right * 10 + temp % 10;
            temp  /= 10;
        }
        return left * p + right % p;
    }

三、例题 题：866. 回文素数

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

示例 1：

输入：6
输出：7

示例 2：

输入：8
输出：11

示例 3：

输入：13
输出：101

提示：

1 <= N <= 10^8
答案肯定存在，且小于 2 * 10^8。

解：

解题思路：看模板

AC代码：

class Solution {
    public int primePalindrome(int n) {
        while(true) {
            if(isPal(n)) {
                if(isPrime(n)) return n;
                else n = nextPal(n);
            }else {
                n ++;
            }
        } 
    }
    // 判断素数
    boolean isPrime(int n) {
        if(n <= 1) return false;
        if(n == 2) return true;   // 一定要先写2是素数
        if((n & 1) == 0) return false; // 然后再写偶数不是素数     
        for(int i = 3; i * i <= n; i += 2) {
            if(n % i == 0) return false;
        }
        return true;
    }
    // 判断回文
    boolean isPal(int n) {
        if(n < 0 || (n % 10 == 0 && n != 0)) return false;
        int reverN = 0; // 将n与反转后reverN进行比对
        while(n > reverN) {
            reverN = reverN * 10 + n % 10;
            n = n / 10;
        }
        return n == reverN || n == reverN / 10; // 奇偶长度情况
    }
    // 计算数字的位数
    int numlen(int n) {
        n = Math.abs(n);
        if(n < 10) return 1;
        else return numlen(n / 10) + 1;
    }
    // 下一个回文数(已知一个回文数)
    int nextPal(int n) {
        int len = numlen(n);
        int p = (int)(Math.pow(10, len / 2));
        int left = n / p + 1; // 得到左边一半 + 1；
        // 计算右一半
        int right = 0; int temp = left;
        while(temp > 0) {
            right = right * 10 + temp % 10;
            temp  /= 10;
        }
        return left * p + right % p;
    }
}

题：剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。
n 不超过1690。

解：

解题思路：动态规划
d p [ i ] = min ⁡ ( d p [ a ] × 2 , d p [ b ] × 3 , d p [ c ] × 5 ) dpleft[ i right] =min left( dpleft[ a right] times 2,dpleft[ b right] times 3,dpleft[ c right] times 5 right) dp[i]=min(dp[a]×2,dp[b]×3,dp[c]×5)

AC代码：

class Solution {
    public int nthUglyNumber(int n) {
       int a = 0, b = 0, c = 0; // 三指针 
       int[] dp = new int[n]; // 存储第几个丑数
       dp[0] = 1;
       for(int i = 1; i < n; i ++) {
           dp[i] = Math.min(dp[a] * 2, Math.min(dp[b] * 3, dp[c] * 5));
           // 判断a，b，c的贡献
           if(dp[a] * 2 == dp[i]) a ++;
           if(dp[b] * 3 == dp[i]) b ++;
           if(dp[c] * 5 == dp[i]) c ++;
       }
       return dp[n - 1]; 
    }
}

时间复杂度 O(N) ： 其中 N = n ，动态规划需遍历计算 dp 列表。空间复杂度 O(N) ： 长度为 N 的 dp 列表使用 O(N) 的额外空间。