Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /************************************************
- Programmer : Muhammad Azri bin Jasni @ Abdul Rani
- Program : project euler problem 12.cpp
- Link : http://projecteuler.net/problem=12
- Description: Knowledge of triangle and square number may needed.
- Note : I... didn't check for square number.... why is it correct answer?
- *************************************************
- 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
- 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?
- *************************************************
- At first, we can think of brute strength of finding each triangle number, then find divisor while counting it until the triangle number.
- But it is easy to imagine how much calculation may needed at large number.
- Project Euler was designed to be solved within a minute, so... -Google-ing references-
- 1. Find triangle number, from 1 until condition reach (divisor = 500)
- a. formula : Tn = n*(n+1)/2
- 2. Divisors are also factors. calculate the no of factors.
- 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.
- You know, 28 have factor 1 that paired with 28, factor 2 paired with 14, factor 4 paired with 7.
- 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...
- *************************************************
- http://www.cplusplus.com/reference/clibrary/cmath/modf/
- 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
- */
- #include <iostream>
- #include <math.h>
- using namespace std;
- /*
- triangle number function
- will return the triangle number based on n
- */
- long triangleNumber(int n)
- {
- return n*(n+1)/2;
- }
- /*
- square number function
- return true if its square number
- */
- bool squareNumber(long number)
- {
- double * a;
- if ( modf(sqrt(number),a) == 0 )
- return true;
- return false;
- }
- /*calculate no of factors/divisors*/
- int noOfFactor(long number)
- {
- int count=0;
- /*if (squareNumber(number))
- {
- for (long i=1;i<=number;i++)
- {
- if (number%i==0)
- count+=1;
- }
- }
- else*/
- {
- for (long i=1;i<=sqrt(number);i++)
- {
- if (number%i==0)
- count+=2;
- }
- }
- return count;
- }
- int main()
- {
- int factorCounter = 0;
- int n;
- for (n = 1; factorCounter<=500; n++)
- {
- factorCounter = noOfFactor( triangleNumber(n) );
- }
- cout << triangleNumber(n-1) << endl;
- cout << factorCounter << endl;
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement