文章目錄
- 素數的概念
- 試除法判斷素數
- 例題決議
- 回文素數
- 丑數
- 丑數 II
素數的概念
素數即質數，是指在大于1的自然數中，除了1和它自身外，不能被其他自然數整除的數，
試除法判斷素數
首先，一個數的因數都是成對出現的：例如12的因數有3和4,2和6;
所以我們可以只列舉每一對中較小的那一個，假設較小的為d，較大的為n/d;
所以說 ：d<(n/d) 那么進行化簡 d^2<=n 最終得到的就是d<=sqrt(n);時間復雜度就從O(n) 優化成為了 O(sqrt(n)
時間復雜度是：O(sqrt(n))
bool judge(int n ){
if(n<2) return false;//質數是從2開始的
for(int i=2;i<=n/i;i++){
if(n%i==0) return false;
}
return true;
}
例題決議
題目來自于leetcode ，題目講解來自Acwing，同時歡迎大家加入Acwing社區
回文素數
題目描述
求出大于或等于 N 的最小回文素數，
回顧一下，如果一個數大于 1，且其因數只有 1 和它自身，那么這個數是素數，
例如，2，3，5，7，11 以及 13 是素數，
回顧一下，如果一個數從左往右讀與從右往左讀是一樣的，那么這個數是回文數，
例如，12321 是回文數
思路
我們可以從最小的回文數開始逐一列舉，直到找到一個大于等于N的素數為止，現在判斷一個數是不是素數，可以使用上面介紹的試除法判斷素數來進行判斷，那么現在如何判斷一個數是不是回文數呢，
而所有的數的位數只有兩種可能
-
奇數位
- 如果說原來的數是 abc 那么說反轉之后就是 abcba
,我們可以很容易看到，只需要把原來的數字反轉之后，去除掉第一位拼接在原來的字串后面就是回文串，然后判斷這個新得到的數是不是質數，就可以得到答案
- 如果說原來的數是 abc 那么說反轉之后就是 abcba
-
偶數位
- 如果說原來的數是 ab ，那么說反轉之后就是 abba, 我們可以看到奇數位和偶數位相加之后，是相等的，而對于這種數而言，一定是11的倍數，也就是說一定不是質數，也就沒有判斷的必要了，
代碼
class Solution {
int get(int x){
String a = String.valueOf(x);
String b = new StringBuilder(a).reverse().toString();
return Integer.valueOf(a+b.substring(1));
}
public boolean isPrime(int x){
if(x<2) return false;
for(int i = 2;i<=x/i;i++){
if(x%i==0){
return false;
}
}
return true;
}
public int primePalindrome(int n) {
if(n>7 && n<=11){
return 11;
}
for(int i = 1;true;i++){
int x = get(i);
if(x>=n && isPrime(x)){
return x;
}
}
}
}
丑數
題目描述
判斷一個數是不是丑數
思路
只需要判斷把 2 3 5 每個因子除干凈之后，判斷n是不是1即可
代碼
class Solution {
public boolean isUgly(int n) {
if(n <= 0 ) return false;
while(n % 2 ==0 ) n/=2;
while(n % 3 == 0) n/=3;
while(n % 5 == 0) n/=5;
return n==1;
}
}
丑數 II
題目描述
我們把只包含質因子 2、3 和 5 的數稱作丑數（Ugly Number），求按從小到大的順序的第 n 個丑數，
思路
s1 = 1*2,2*2,3*2,4*2
s2 = 1*3,2*3,3*3,4*3
s3 = 1*5,2*5,3*5,4*5
ans = 1 U s1 U s2 U s3
因為題目中說明，丑數只包含質因子2、3、5，所以我們很容易得到上面的4個集合，注意題目中說明了1是第一個丑數，丑數實際上是就是這幾個集合的并集，現在關鍵是要從小到大進行排列，我們可以用三個指標來移動這三個集合，每個集合的后一項實際上就是前一項的基礎之上乘以相應的倍數，我們每次只需要把三個指標所指向的位置中最小的一個放入陣列中就行了，
代碼
class Solution {
public int nthUglyNumber(int n) {
int[] res = new int[n];
int i ,j, k;
i = j = k =0;
res[0] = 1;
for(int u = 1;u<n;u++){
int t = Math.min(res[i]*2,Math.min(res[j]*3,res[k]*5));
res[u] =t;
if(t == res[i] * 2) i++;
if(t == res[j] * 3) j++;
if(t == res[k] * 5) k++;
}
return res[n-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/340675.html
標籤：其他