title: Down to zero problem - getting time exceeded error
body: <p>Trying to solve hackerrank <a href="https://www.hackerrank.com/challenges/down-to-zero-ii" rel="nofollow">problem</a>.</p>
  
  <p>You are given Q queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a×b(a≠1, b≠1), we can change N=max(a,b) or decrease the value of N by 1.
  Determine the minimum number of moves required to reduce the value of N to 0.</p>
  
  <p>I have used BFS approach to solve this. </p>
  
  <p>a. Generating all prime numbers using seive</p>
  
  <p>b. using prime numbers I can simply avoid calculating the factors</p>
  
  <p>c. I enqueue -1 along with all the factors to get to zero.</p>
  
  <p>d. I have also used previous results to not enqueue encountered data.</p>
  
  <p>This still is giving me time exceeded. Any idea? Added comments also in the code.</p>
  
  <pre><code>import math
  #find out all the prime numbers
  primes = [1]*(1000000+1)
  primes[0] = 0
  primes[1] = 0
  for i in range(2, 1000000+1):
    if primes[i] == 1:
      j = 2
      while i*j &lt; 1000000:
        primes[i*j] = 0
        j += 1
  
  n = int(input())
  for i in range(n):
    memoize= [-1 for i in range(1000000)]
    count = 0
    n = int(input())
    queue = []
    queue.append((n, count))
    while len(queue):
      data, count = queue.pop(0)
      if data &lt;= 1:
        count += 1
        break   
      #if it is a prime number then just enqueue -1
      if primes[data] == 1 and memoize[data-1] == -1:
        queue.append((data-1, count+1))
        memoize[data-1] = 1
        continue
      #enqueue -1 along with all the factors
      queue.append((data-1, count+1))
      sqr = int(math.sqrt(data))
      for i in range(sqr, 1, -1):
        if data%i == 0:
          div = max(int(data/i), i)
          if memoize[div] == -1:
            memoize[div] = 1
            queue.append((div, count+1))
    print(count)
  </code></pre>