Wow this is a great optimization! You're under-selling it :) It changes the memory requirement from O(π(n)) to O(π(√n)), e.g. after processing numbers up to 100

Wow this is a great optimization! You're under-selling it :) It changes the memory requirement from O(π(n)) to O(π(√n)), e.g. after processing numbers up to 100, the internal state in the OP's algorithm is: q = 101 D = {'102': [3, 2], '105': [7, 5], '121': [11], '169': [13], '289': [17], '361': [19], '529': [23], '841': [29], '961': [31], '1369': [37], '1681': [41], '1849': [43], '2209': [47], '2809': [53], '3481': [59], '3721': [61], '4489': [67], '5041': [71], '5329': [73], '6241': [79], '6889': [83], '7921': [89], '9409': [97]} while with your "small change", the state is just: q = 101 S = 121 r = 11 D = {'102': [3, 2], '105': [7, 5]}