안녕하세요 알통몬입니다. 공감 및 댓글은 포스팅 하는데 아주아주 큰 힘이 됩니다!! 포스팅 내용이 찾아주신 분들께 도움이 되길 바라며 더 깔끔하고 좋은 포스팅을 만들어 나가겠습니다^^
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
이 삼각수들의 약수를 구해봅시다.
<tt> 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</tt>
위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.
그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?
저는 결과 얻는데 한 10분 걸린 거 같아요.
제가 푼 답 :
public class Question12 {
public static void main(String[] args) {
int triangular_number = 1;
int num = 2;
int divisor = 0;
while(divisor<500){
divisor = 0;
triangular_number += num;
for(int i=1; i<=triangular_number; i++){
if(triangular_number%i==0){
divisor++;
}
}
num ++;
}
System.out.println(triangular_number);
}
}
고속 약수 구하기 알고리즘
import java.util.*; public class HighlyDivisibleTriangularNumber { public int smallestTrianglurUnder(int restrictSize) { int previousTriNum, n=0, tri=0, sizeOfAliquot; while(true){ previousTriNum = tri; n++; tri = getNthTriNum(previousTriNum,n); sizeOfAliquot = getSizeOfAliquot(tri); if(sizeOfAliquot >= restrictSize){ return tri; } } } int getSizeOfAliquot(int triangular) { Map<Integer,Integer> aliquotsUnderSqrt = new HashMap<Integer, Integer>(); for(int i=1;i<=Math.sqrt(triangular);i++){ if(triangular % i == 0){ aliquotsUnderSqrt.put(i, i); } } Map<Integer, Integer> aliquots = new HashMap<Integer, Integer>(); aliquots.putAll(aliquotsUnderSqrt); for(int key : aliquotsUnderSqrt.keySet()){ int aliquot = aliquotsUnderSqrt.get(key); if(triangular % aliquot == 0){ int val = triangular / aliquot; aliquots.put(val, val); } } return aliquots.size(); } int getNthTriNum(int previousTriNum, int n) { return previousTriNum + n; } }