document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /************************************************
  2. Programmer : Muhammad Azri bin Jasni @ Abdul Rani
  3. Program    : project euler problem 12.cpp
  4. Link       : http://projecteuler.net/problem=12
  5. Description: Knowledge of triangle and square number may needed.
  6. Note       : I... didn\'t check for square number.... why is it correct answer?
  7. *************************************************
  8.  
  9. 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:
  10.  
  11. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  12.  
  13. Let us list the factors of the first seven triangle numbers:
  14.  
  15.      1: 1
  16.      3: 1,3
  17.      6: 1,2,3,6
  18.     10: 1,2,5,10
  19.     15: 1,3,5,15
  20.     21: 1,3,7,21
  21.     28: 1,2,4,7,14,28
  22.  
  23. We can see that 28 is the first triangle number to have over five divisors.
  24.  
  25. What is the value of the first triangle number to have over five hundred divisors?
  26. *************************************************
  27. At first, we can think of brute strength of finding each triangle number, then find divisor while counting it until the triangle number.
  28. But it is easy to imagine how much calculation may needed at large number.
  29. Project Euler was designed to be solved within a minute, so...  -Google-ing references-
  30.  
  31. 1. Find triangle number, from 1 until condition reach (divisor = 500)
  32.    a. formula : Tn = n*(n+1)/2
  33. 2. Divisors are also factors. calculate the no of factors.
  34.    a. Can be simplified by reaching only to sqrt(num). This is because of all factors are pairs. So, for every factor, add 2 instead into the factor counter.
  35.       You know, 28 have factor 1 that paired with 28, factor 2 paired with 14, factor 4 paired with 7.
  36.    b. The sqrt(num) can only works if it is not a sqrt num. I don\'t understand this, but that what I got from my reading. So check for this...
  37. *************************************************
  38. http://www.cplusplus.com/reference/clibrary/cmath/modf/
  39. I can\'t think well how I want to check for square number. So I thought about square-root-ing the number and check if there is fractional part of it
  40. */
  41. #include <iostream>
  42. #include <math.h>
  43. using namespace std;
  44.  
  45. /*
  46. triangle number function
  47. will return the triangle number based on n
  48. */
  49. long triangleNumber(int n)
  50. {
  51.      return n*(n+1)/2;
  52. }
  53.  
  54. /*
  55. square number function
  56. return true if its square number
  57. */
  58. bool squareNumber(long number)
  59. {
  60.      double * a;
  61.      if ( modf(sqrt(number),a) == 0 )
  62.         return true;
  63.      return false;
  64. }
  65.  
  66. /*calculate no of factors/divisors*/
  67. int noOfFactor(long number)
  68. {
  69.     int count=0;
  70.     /*if (squareNumber(number))
  71.     {
  72.        for (long i=1;i<=number;i++)
  73.        {
  74.            if (number%i==0)
  75.               count+=1;
  76.        }
  77.     }
  78.     else*/
  79.     {
  80.        for (long i=1;i<=sqrt(number);i++)
  81.        {
  82.            if (number%i==0)
  83.               count+=2;
  84.        }
  85.     }
  86.     return count;
  87. }
  88.  
  89. int main()
  90. {
  91.     int factorCounter = 0;
  92.     int n;
  93.     for (n = 1; factorCounter<=500; n++)
  94.     {
  95.         factorCounter = noOfFactor( triangleNumber(n) );
  96.     }
  97.     cout << triangleNumber(n-1) << endl;
  98.     cout << factorCounter << endl;
  99.     system("pause");
  100.     return 0;
  101. }
');