`
mysh
  • 浏览: 28865 次
  • 性别: Icon_minigender_1
  • 来自: 福州
社区版块
存档分类
最新评论

Project Euler p12 - Highly divisible triangular number

阅读更多

 

http://projecteuler.net/problem=12

 

求因数个数大于500的数, 关键在于下面两个隐藏的条件

triangle(i)=i*(i+1)/2

divisors(a*b)=divisors(a)*divisors(b)

 

countDivisors 其实它还可以优化成递归求解, 而不是一个个去数, 不过量不大, 就算了.

 

76576500 576

23 ms

 

 

@Test  
public void t1() {  
    int d;  
    for (int i = 7; i < Integer.MAX_VALUE; i++) {  
        if (i % 2 == 0) d = countDivisors(i / 2) * countDivisors(i + 1);  
        else d = countDivisors(i) * countDivisors((i + 1) / 2);  
        if (d >= 500) {  
            System.out.println(i * (i + 1) / 2 + " " + d);  
            return;  
        }  
    }  
}  
  
private int countDivisors(int n) {  
    int c = 1;
    double sqrt = Math.sqrt(n);  
    for (int i = 2; i <= sqrt; i++) {  
        if (n % i == 0) {
            c += 2;  
            if (i == sqrt) c--;
        }
    }  
    return c+1;  
}  

 

1
2
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics