python - down to zero hackerrank getting time exceeded -

trying solve hackerrank problem.

you given q queries. each query consists of single number n. can perform 2 operations on n in each move. if n=a×b(a≠1, b≠1), can change n=max(a,b) or decrease value of n 1. determine minimum number of moves required reduce value of n 0.

i have used bfs approach solve this.

a. generating prime numbers using seive

b. using prime numbers can avoid calculating factors

c. enqueue -1 along factors zero.

d. have used previous results not enqueue encountered data.

this still giving me time exceeded. idea? added comments in code.

import math #find out prime numbers primes = [1]*(1000000+1) primes[0] = 0 primes[1] = 0 in range(2, 1000000+1):   if primes[i] == 1:     j = 2     while i*j < 1000000:       primes[i*j] = 0       j += 1  n = int(input()) in range(n):   memoize= [-1 in range(1000000)]   count = 0   n = int(input())   queue = []   queue.append((n, count))   while len(queue):     data, count = queue.pop(0)     if data <= 1:       count += 1       break        #if prime number enqueue -1     if primes[data] == 1 , memoize[data-1] == -1:       queue.append((data-1, count+1))       memoize[data-1] = 1       continue     #enqueue -1 along factors     queue.append((data-1, count+1))     sqr = int(math.sqrt(data))     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) 

there 2 large causes of slowness code.

clearing array slower clearing set

the first problem line:

memoize= [-1 in range(1000000)] 

this prepares 1 million integers , executed each of 1000 test cases. faster approach use python set indicate values have been visited.

unnecessary loop being executed

the second problem line:

if primes[data] == 1 , memoize[data-1] == -1: 

if have prime number, , have visited number, slow loop searching prime factors never find solutions (because prime).

faster code

in fact, improvement due using sets don't need prime testing code , following code passes tests within time limit:

import math n = int(input()) in range(n):   memoize = set()   count = 0   n = int(input())   queue = []   queue.append((n, count))   while len(queue):     data, count = queue.pop(0)     if data <= 1:       if data==1:         count += 1       break        if data-1 not in memoize:         memoize.add(data-1)         queue.append((data-1, count+1))     sqr = int(math.sqrt(data))     in range(sqr, 1, -1):       if data%i == 0:         div = max(int(data/i), i)         if div not in memoize:           memoize.add(div)           queue.append((div, count+1))   print(count)