Problem Analysis
The n-th triangular number is T(n) = n(n+1)/2, the sum of the first n natural numbers. We want the first such number with more than 500 divisors. The key tool is the divisor-counting function d(m): if m has the prime factorization m = p1^a1 * p2^a2 * ... * pk^ak, then d(m) = (a1+1)(a2+1)...(ak+1). The reasoning is combinatorial: every divisor is built by choosing, independently, an exponent from 0 to ai for each prime, so the product of the (ai+1) choice-counts gives the total number of divisors. This is far cheaper than enumerating divisors directly.
To factor an individual number we use trial division up to the square root: any composite m has a factor no larger than sqrt(m), so testing divisors d while d*d <= m suffices, with any residue greater than 1 being a prime that occurs once. This costs O(sqrt(m)) per number. The structural observation that makes the search fast is that n and n+1 are coprime (consecutive integers share no common factor), and the divisor function is multiplicative: d(a*b) = d(a)*d(b) when gcd(a,b)=1. Since exactly one of n, n+1 is even, T(n) splits into two coprime halves, and we can count divisors on numbers roughly half the magnitude of T(n) itself.
Solution Approach
Algorithm 0: Multiplicative split into coprime halves (p0012_s0.py, p0012_s0_c)
This approach exploits multiplicativity directly. At each step I look at the parity of i. If i is even, T(i) = (i/2)*(i+1); if i is odd, T(i) = i*((i+1)/2). In both cases the two factors are coprime, so d(T(i)) = num_factors(first) * num_factors(second). The dividing-by-two folds the /2 of the triangular formula into whichever factor is even, keeping both operands exact integers and roughly half the size of T(i). The loop advances i and recomputes triangle_number = i*(i+1)/2 at the bottom, so the value returned when the divisor count first exceeds the target is correct. Factoring two smaller numbers instead of one large one is the entire payoff: trial division cost scales with the square root, so two halves are cheaper than the whole.
The Python and C versions are logically identical. C uses long long for the triangle number as a defensive choice against overflow, and folds the leftover-prime case into result *= 2 (an unconsumed residue is a prime with exponent 1, contributing a factor of 2). Python's prime_factorization returns explicit (prime, exponent) tuples, which num_factors then reduces to the product of (exp+1).
Algorithm 1: Direct trial division per triangular number (p0012_s1.py, p0012_s1_c)
This is the straightforward baseline. For each T(i) I factor the whole number by trial division and compute d(T(i)) from the exponents, advancing through triangular numbers until the count exceeds the target. There is no coprime split; each triangular number is treated as an independent factorization problem. The code is simpler - the loop condition is just num_factors(triangle_number) < num_divisors - but it factors a number twice as large as either half in Algorithm 0, doing more work per step.