Can anyone help me with doing problem 12 on project euler? The question is asking which triangle number has more than 500 factors. The first few triangle numbers are: 1, 3, 6, 10, 15, 21, 28 ... Hope you understand the pattern, cause a can't explain it in words vary well.
Anyways I written the code in C, and it's just too slow. Here's an english version I wrote for easyness:
Generate the triangle number under (500^2) loop until the triangle number's factors is more than 500 generate next triangle number return triangle number to find how many factors a number has: divide number by prime number going from lowest to higher until it divides evenly if the result is prime, tally the prime number and the result if the result is not prime, tally the prime number and the result becomes the number and loop back to the "divide number by pr..." stage add 1 and multiply everything in the tally that is not zero the product is the number of factors to generate prime numbers: start with 2 and 3 int n = 1, prime = 0 while prime is not prime increase n if called on an odd time loop back with prime = 6n-1 on every odd time and loop back with prime = 6n+1 on every even time return prime and finally to check if a number is prime: if number is under 2, its not prime //this is a prime sieve if number is 2, its prime if number is divisible by 2, its not prime if number is 3, its prime if number is divisible by 3, its not prime ... int count = what ever last sieve was while count < sqrt number if number mod count = 0 return 0 (not prime) return 1 (is prime)
I'm going to attach the c version becouse its 341 lines long!
I think the time is being waisted mostly at the isprime step, or the countdiv (factoring) step.
Any suggestions to speed this puppy up? Thanks alot.