"""
The sequence of triangle numbers is generated by adding the natural numbers. 
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first 
ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
2*2*7


factoring 36
2, 18
2, 9
3, 3

1, 2, 3, 4, 9, 12, 18, 36

factoring 45
3, 15
3, 5

1, 3, 5, 9, 15, 45

factor by pulling out prime, finding remainder then dividing the orignal by the remainder
to find the opposite factor


We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

"""
import time

def main():
	start = time.time()
	
	#find all primes less than 2 million to start...
	primeList = findPrimes(500000, 500000)
	factorTriangularNumbers(primeList, 25s)

	timeElapsed = (time.time()-start)
	print timeElapsed

def factorTriangularNumbers(primeList, maxDivisors):
	notFound = True
	currentTriangular = 2
	triangularSum = 1
	while (notFound):
		triangularSum += currentTriangular
		holdingSum = triangularSum
		factorList = []
		#factoring
		for ind, val in enumerate(primeList):
			factorCurrent = True
			while (factorCurrent):	
				if (val and isItAFactor(ind, holdingSum)):
					holdingSum = holdingSum/ind
					factorList.append(holdingSum)
					factorList.append(triangularSum/holdingSum)
				else:
					factorCurrent = False
			if (ind > holdingSum/2): break
		print currentTriangular
		print triangularSum
		print factorList
		print ""
		if (len(factorList) >= maxDivisors):
			notFound = False
		currentTriangular+=1

def isItAFactor(x, toFactor):
    if (toFactor % x ==0):
        return True
    else:
        return False

def findPrimes(limit, numPrimesWanted):
	maxNumbersToCheck = limit
	if (maxNumbersToCheck % 2 is 0):
		maxNumbersToCheck += 1
	primeList = [True] * maxNumbersToCheck
	primeList[0] = None
	primeList[1] = None
	primeCount = 0
	primeSum = 0
	for ind, val in enumerate(primeList):
		if (val == True):
			primeSum += ind
			primeCount += 1
			multiple = ind*2
			while (multiple < maxNumbersToCheck):
				primeList[multiple] = False
				multiple +=ind
		if (primeCount >= numPrimesWanted):
			return primeCount
	return primeList




if __name__ == "__main__":
    main()

#142913828920

