Prime Factor Sieve

This probably isn't new and you can find this in many places, but I discovered it on my own without looking it up anywhere so I am pretty proud of myself.

Factoring numbers down to their prime factor fingerprint is a very interesting matter.  It can take an enormous amount of time with large numbers, hence there is security for the internet.  However with this algorithm computing prime factors of numbers up to some target is fairly quick.  The algorithm is O(n³).

We begin with the Sieve of Eratosthenes, solving for 1 < x <= n and modify it so that instead of crossing out numbers we append the prime factors to them.  This creates a list of all the unique prime factors for every x.  Then we go through all of the composites from smallest to largest and divide the number by its unique prime factors.  We then take the quotients prime factors and append it to x's list.  The Sieve of Eratosthenes runs in O(nloglogn).  The second part of the algorithm runs n times and is division which runs n², hence the Algorithm is n³ + nloglogn. which is O(n³).  The real killer of this algorithm is the space complexity rather than the time complexity.

Bouncy Numbers

Recently I have done a lot of Project Euler problems and I solved problem 112.

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

 I found that there are two ways to solve this problem efficiently.  The first takes two passes through the number to determine if it is bouncy.  The other takes only one pass.  The first method determines if the number is increasing, then decreasing, and if it is neither then it is bouncy.  The second just determines if it is bouncy.

To determine if a number is increasing or decreasing, I used the same algorithm but just switched the comparison operator. The Algorithm is starting from the right hand side of the number compare the last two digits, for increasing the digit prior should be less than the succeeding digit and vice versa for decreasing.
Psuedo-Code:
  
  i //i is the number we are checking
  
  while(i > 9){
    j = i mod 10
    i /= 10
    k = i mod 10
    if(k < j)  //This checks if the number is decreasing.
      return false
  }
  
  return true


The other method uses one pass to check if the number is bouncy.
It checks the difference between the digits and checks for a switch in the sign.
If the number is increasing (12345) the difference between the digits, subtracting the right from the left (2 - 3 = -1), is always negative. Decreasing the difference is always positive.  If the number is bouncy then there will be a change a of sign.  Detecting that change of sign can be done with an xor.  The only tricky part is dealing with zeros.  Zeros have to be skipped over because they can be apart of both increasing and decreasing numbers.

Psuedo-Code:

  

  i

  r = 0




  while(r == 0){ // gets r to first non-zero

    j = i mod 10

    i /= 10
    k = i mod 10
    r = k - j
  while(i > 9){
    j = i mod 10
    i /= 10    k = i mod 10
    p = k - j
    if(p xor r < 0 )  //This checks for a sign change
      return true
  }

  return false

These are both fast but the second method is 60% faster than the first method.