Print prime number:
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.
Nubmer Expressible(This problem is still called ugly number):
Given a prime set, we call “prime expressible” if a number can be factorized only using given prime numbers. Find n-th big expressible number. For example, if prime set = {2, 3}, expressible number = {1,2,3,4,6,8, 9, 12…}, non-expressible number = {5, 10… }
For printing prime number, we can use Sieve of Eratosthenes to solve. Space complexity is O(N), time complexsity is O(NloglogN)
For number expressible, it has the similar way which we store expressible number in a TreeSet.
At the TreeSet only has {2, 3}. Remove the min element in TreeSet, and use it to multiply set {2, 3}. We get 4, 6. Put 4, 6, in TreeSet. It will be {3, 4, 6}.
Then we get min element in TreeSet which is 3. Use 3 to multiply set {2, 3}. We get 6, 9. Put 6, 9 in TreeSet, It will be {4, 6, 9}.
We iterate this step for n times. Then we can get the Nth expressible number. Time complexity is O(NlogN), space is O(N).
There is another O(nk) time and space solution. Each time, calculate each prime time where it is at by its index. Find the minimum value, add in the array. Then move the index to next ugly number. The process is like below:
check my code on github: Print prime number, Nubmer Expressible, Ugly Number O(n) solution