|
| 1 | +packageProjectEuler; |
| 2 | +/** |
| 3 | + * The sequence of triangle numbers is generated by adding the natural numbers. |
| 4 | + * So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. |
| 5 | + * The first ten terms would be: |
| 6 | + * <p> |
| 7 | + * 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... |
| 8 | + * <p> |
| 9 | + * Let us list the factors of the first seven triangle numbers: |
| 10 | + * <p> |
| 11 | + * 1: 1 |
| 12 | + * 3: 1,3 |
| 13 | + * 6: 1,2,3,6 |
| 14 | + * 10: 1,2,5,10 |
| 15 | + * 15: 1,3,5,15 |
| 16 | + * 21: 1,3,7,21 |
| 17 | + * 28: 1,2,4,7,14,28 |
| 18 | + * We can see that 28 is the first triangle number to have over five divisors. |
| 19 | + * <p> |
| 20 | + * What is the value of the first triangle number to have over five hundred divisors? |
| 21 | + * <p> |
| 22 | + * link: https://projecteuler.net/problem=12 |
| 23 | + */ |
| 24 | +publicclassProblem12 { |
| 25 | + |
| 26 | +/** |
| 27 | + * Driver Code |
| 28 | + */ |
| 29 | +publicstaticvoidmain(String[]args) { |
| 30 | +assertsolution1(500) ==76576500; |
| 31 | + } |
| 32 | + |
| 33 | +/* returns the nth triangle number; that is, the sum of all the natural numbers less than, or equal to, n */ |
| 34 | +publicstaticinttriangleNumber(intn) { |
| 35 | +intsum =0; |
| 36 | +for (inti =0;i <=n;i++) |
| 37 | +sum +=i; |
| 38 | +returnsum; |
| 39 | + } |
| 40 | + |
| 41 | +publicstaticintsolution1(intnumber) { |
| 42 | +intj =0;// j represents the jth triangle number |
| 43 | +intn =0;// n represents the triangle number corresponding to j |
| 44 | +intnumberOfDivisors =0;// number of divisors for triangle number n |
| 45 | + |
| 46 | +while (numberOfDivisors <=number) { |
| 47 | + |
| 48 | +// resets numberOfDivisors because it's now checking a new triangle number |
| 49 | +// and also sets n to be the next triangle number |
| 50 | +numberOfDivisors =0; |
| 51 | +j++; |
| 52 | +n =triangleNumber(j); |
| 53 | + |
| 54 | +// for every number from 1 to the square root of this triangle number, |
| 55 | +// count the number of divisors |
| 56 | +for (inti =1;i <=Math.sqrt(n);i++) |
| 57 | +if (n %i ==0) |
| 58 | +numberOfDivisors++; |
| 59 | + |
| 60 | +// 1 to the square root of the number holds exactly half of the divisors |
| 61 | +// so multiply it by 2 to include the other corresponding half |
| 62 | +numberOfDivisors *=2; |
| 63 | + } |
| 64 | +returnn; |
| 65 | + } |
| 66 | +} |