# triangluar number 에서 약수가 500개 이상인 수는?

문제는 간단하다. triangluar number 중에서 약수가 500개 이상인 수를 찾는거다. 삼각수란 (링크) : http://ko.wikipedia.org/wiki/%EC%82%BC%EA%B0%81%EC%88%98  핵심은.. 1,000,000 같은 큰 수에대한 약수를 구하는 것 같은데, 약수를 찾는 알고리즘은 간단하게 검색만해도 여러개 나온다. 그중 하나를 골라서 문제를 풀었다. 약수 알고리듬 (링크) :  http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

#include <iostream> #include <Windows.h> using namespace std; int Calc_div(long long number); int number_of_divisors(long long n); int divisors(long long x); // Divisor cacl # 1 int Calc_div(long long number) { int divisorCount = 0; for (long long i = 1; i <= number / 2; ++i) if (number%i == 0) divisorCount++; divisorCount++; return divisorCount; } // Divisor cacl # 2 int number_of_divisors(long long n) { int counter, i; for (counter = 0, i = 1; (!(i == n) && !(n%i) && (counter++)) || i <= (n / 2); i++); return ++counter; } // Divisor cacl # 3 int divisors(long long x) { long long limit = x; int numberOfDivisors = 1; for (int i(1); i < limit; ++i) { if (x % i == 0) { limit = x / i; numberOfDivisors++; } } return numberOfDivisors * 2; } void main() { long long triangluarNumber = 0; long long naturalNum = 1; while (1) { triangluarNumber += naturalNum; if (divisors(triangluarNumber) >= 500){ break; } naturalNum++; } cout << "Answer is :" << triangluarNumber << endl; system("pause"); }