Euler#12, what's wrong with my Python program? -

the 12th problem :

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

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

let list factors of first 7 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 can see 28 first triangle number have on 5 divisors.

what value of first triangle number have on 5 hundred divisors?

---

my program in python 3.4

def nfactor(n):     k=2     c=0     while k<=n:         if n%k==0:           n=n//k           c+=1         else:             k=k+1            return c  a=1     in range(10**6):     a+=i     if nfactor(a)>=500:         print(a)         break 

---

i waited more 10 minutes , never have answer. , own program not bad , must run in seconds.. makes me crazy lol didn't find mistake.

can me please?

thank in advance !

---

edit

my solution :

import math  def nfactor(n):     if n==1:         return 1     else:         c=0          in range(1, int(math.sqrt(n)+1)):             if n%i==0:                 c+=1         return c*2  a=0     in range(1,10**6):     a+=i     if nfactor(a)>=500:         print(a)         break 

you not any output.

your last value of a 499999500001 while smallest number nfactor(..) 500, 2^500 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376

---

a few hints (i have working example runs in less 1 second guess posting here spoiler):

• as (deleted) answer pointed out, given count of prime factors number, number of divisors of number product of (counts of each prime factor plus one), i.e. if prime factor p appears n times, can build n+1 products from 0 p^n , combine different powers of primes.

• as @nightshadequeen points out, once have calculated prime factorization of number n, keep in cache (i use dict mapping n dict maps prime number number of times occurs). when asked calculate set of prime factors given number, first check cache, start scanning 2 upwards see if can find first factor. call function recursively n divided first factor etc.

• for finding prime factors of n, there no need go n, can stop @ sqrt(n)

• when finding prime factors (k in function nfactor(..)), can check k=2, k=3 (i.e. if 2 divides n, if 3 divides n etc.) , increment k in steps of 2 (only test odd values of k after k=2)

• as mentioned in comment above, start a=1 , use range(1,10**6) instead i

not used in solution; found using favourite search engine:

• the i'th triangle number a = * (i+1) / 2 can combine prime factors of i , i+1 (removing 1 occurrence of 2). since i , i+1 not share common prime factors can derive number of divisors of a number of divisors of i , i+1.