Problem 47

p47.py

def list_primality_modified(n):
	result = [0] * (n + 1) #Initialize an array of length n+1
	for i in range(2,int((n)) + 1): #We want to go all the way to the length instead of sqrt(n) 
					#to include all prime factors
		if result[i] == 0: #If this value has not been marked yet, continue
			for j in range(2 * i, len(result), i):
				result[j] += 1 #Add all the prime factors
	return result
#We will obtain a list where array[x] represents the number of prime factors of x,
#if array[x] = 0 then x is a prime