[FWD] Rolex Price

[ProjectEuler] 423

Problem: http://projecteuler.net/problem=423

Super slow code.

Time complexity: O(n^2 / ln(n))

I need to think another way to solve it.

import bisect
import sys

class ConsecutivePrimeCountingFunction():
    def __init__(self):
        self.primes = []
        self.pos = 0
        self._init_primes()
    
    def _init_primes(self):
        #SIEVE_RANGE = 50100
        SIEVE_RANGE = 50000100
        sieve_visited = [False] * SIEVE_RANGE
        sieve_visited[0] = sieve_visited[1] = True
        for i in range(2, SIEVE_RANGE):
            if sieve_visited[i] is False:
                self.primes.append(i)
                for j in range(i + i, SIEVE_RANGE, i):
                    sieve_visited[j] = True
        print('Total prime count:', len(self.primes))
    
    def get(self, n):
        if n >= self.primes[self.pos]:
            self.pos += 1
        return self.pos

    def reset(self):
        self.pos = 0

    def get_directly(self, n):
        return bisect.bisect(self.primes, n)

class Problem():
    def __init__(self):
        self.mod = 1000000007
        self.consecutive_prime_counting_function = ConsecutivePrimeCountingFunction()
    
    def solve(self):
        for n in [50000000]:
            #print(self.S(n))
            print(self.S_lite(n))
    
    def S_lite(self, L):
        max_count = self.consecutive_prime_counting_function.get_directly(L) + 1
        consecutive_map = [0 for count in range(max_count)]
        consecutive_map[0] = 1
        print('Big data structure |consecutive_map| is ready')
        result = 6 # Trivial case for C(1) = 6
        self.consecutive_prime_counting_function.reset()
        
        for i in range(2, L+1):
            if i % 1000 == 0:
                print('Curr:', i, '=>', result)
            pos = self.consecutive_prime_counting_function.get(i)
            prev = consecutive_map[0]
            consecutive_map[0] = 5 * prev
            for count in range(1, max_count):
                curr = consecutive_map[count]
                if curr == 0 and prev == 0:
                    break
                consecutive_map[count] = curr * 5 + prev
                prev = curr
            result = (result + sum(consecutive_map[:pos + 1]) * 6) % self.mod
        return result

    def C(self, n):
        max_count = self.consecutive_prime_counting_function.get_directly(n) + 1
        consecutive_map = [0 for count in range(max_count)]
        consecutive_map[0] = 1

        for i in range(n - 1):
            next_consecutive_map = [0 for count in range(max_count)]
            next_consecutive_map[0] = consecutive_map[0] * 5
            for count in range(1, max_count):
                next_consecutive_map[count] = consecutive_map[count] * 5 + consecutive_map[count - 1]
            consecutive_map = next_consecutive_map
        result = sum(consecutive_map) * 6
        return result

    def S(self, L):
        return sum([self.C(n) for n in range(1, L + 1)]) % self.mod

def main():
    problem = Problem()
    problem.solve()
    
if __name__ == '__main__':
    sys.exit(main())