Calculate Primes & Tile filling

tilling_filling.py

import sys
import string
import fileinput
import pprint

inputs = fileinput.input()

# def calc_prime(N):

vals = [int(N.replace('\n', '')) for N in inputs]
vals = vals[1:]
size = max(vals)

# DP_table = [ for j in range(2)]

brick_arrangement_count = [0 for i in range(size + 1)]
for i in range(size+1):
	if 4 > i >= 0:
		brick_arrangement_count[i] = 1
	else:
		brick_arrangement_count[i] = brick_arrangement_count[i-1] + brick_arrangement_count[i-4]

# primes_less_than = [0 for i in range(brick_arrangement_count[size] + 1)]
# primes = []

# print brick_arrangement_count

def get_primes(N):

	primes = [1 for i in range(0, N+1)]

	for i in range(0, N):
		if i < 2:
			primes[i] = 0
		if primes[i] == 1:
			end = N / i
			for j in range(2, end+1):
				primes[j * i] = 0

	count_primes = [0 for i in range(0,N+1)]
	for i in range(0, N+1):
		if primes[i]:
			count_primes[i] = count_primes[i-1] + 1
		else:
			count_primes[i] = count_primes[i-1]
	return count_primes

count_primes = get_primes(brick_arrangement_count[size])

# for i in range(brick_arrangement_count[size]+1):
# 	if i < 2:
# 		primes_less_than[i] = 0
# 		continue

# 	prime = True
# 	for j in primes:
# 		if i % j == 0:
# 			prime = False
# 	if prime:
# 		primes.append(i)
# 		primes_less_than[i] = primes_less_than[i-1] + 1
# 	else:
# 		primes_less_than[i] = primes_less_than[i-1]

# print primes_less_than
# print brick_arrangement_count
for val in vals:
	# print brick_arrangement_count[val]
	print count_primes[brick_arrangement_count[val]]