Prime Number相关

Prime Number:
只能被1和它本身整除的的数。1不是Prime number.

Ugly Number:
1, 2, 3, 5, 以及能被[2, 3, 5] 整除的数。
直觉上看，除了prime number以外的所有数都能被ugly number整除。

也就是说，两个问题归一了。
无论是find kth prime number或者是kth ugly number. 都属于同一问题，如何有效地在一个int streaming中找到满足条件的数。

进一步分析，如何找到prime number / ugly number
暴力解法就是从1开始每一个数都check, 然后一直check到第kth满足条件的数。这个方法用来找ugly number应该还不错，原因是从[1. x], 基本上所有的数都属于ugly number. 应该能够在~k 的条件下找到ugly number.
去implement一下看看有没有TLE的问题。

oops. 思路off了一点点。重新回到ugly number的定义。 ugly number是只能被2, 3, 5整除的数。但事实上，从1开始的数中，除了能够被2, 3, 5整除的数之外，还有的数的factor是prime number同时他们也能被2, 3, 5整除，所以在check数的同时要排除其能被遇见过的prime number整除的可能性。

果然 TLE了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution: """ @param n: An integer @return: the nth prime number as description. """ def nthUglyNumber(self, n): # write your code here if n == 1: return 1 order = 1 num = 2 primes = [] while order < n: if self.isUglyNumber(num, primes): order += 1 num += 1 return num - 1 def isUglyNumber(self, num, primes): if num % 2 == 0 or num % 3 == 0 or num % 5 == 0: for p in primes: if num % p == 0: return False return True else: primes.append(num) return False

再继续思考一下高级的解法。反构造ugly number，按照ugly number的定义，它只能由ugly number本身构成。所以，我们可以seed = 1, [2, 3, 5]  以 2, 3, 5为factor反构造ugly number的list.

但是这有一个问题是顺序不能够确定？

事实上，原来这是一个DP问题。利用了merge的思想。
ugly number:
constructUglyList2 = 2* ugly[]
constructUglyList3 = 3* ugly[]

constructUglyList5 = 5* ugly[]

merge 3 lists

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution: """ @param n: An integer @return: the nth prime number as description. """ def nthUglyNumber(self, n): # write your code here if n == 1: return 1 ugly = [1] i2, i3, i5, i = 0, 0, 0, 0 while i < n - 1: cur2 = 2 * ugly[i2] cur3 = 3 * ugly[i3] cur5 = 5 * ugly[i5] nthUgly= min(cur2, cur3, cur5) # 这里的i控制的是index if nthUgly != ugly[i]: i += 1 ugly.append(nthUgly) if nthUgly == cur2: i2 += 1 elif nthUgly == cur3: i3 += 1 elif nthUgly == cur5: i5 += 1 # 这里的i控制的是个数 return ugly[i]

总结：
1. positive integer 的构成。
prime number, ugly number, [prime number, ugly number]

2. merge list的思想

3. 到底什么是DP?

4. index值的不同的含义。length，控制循环结束，防止stack overflow。