約数の個数の求め方 2007/12/26

公式

ある整数nが、a^p * b^q * c^r表されるとき、約数の個数は、(p + 1)(q + 1)(r + 1)個

素因数分解
小さい素数から順にわっていく方法を連除法という。

とりあえずJavaのコード。

import java.math.BigInteger;

public class S1 {

public static void main(String[] args) {

int a=360;
int k = 1;

for(int i=2;i<=a;i++){
// 素数になるまで...
if(!isPrime(i)) continue;
int c = 0;
// 割れる間は...
while((a % i) == 0){
a = a / i;
c += 1;
}
System.out.println(i + "^"+c);
k *= c + 1;
}
System.out.printf("約数の個数:%d", k);
}

public static boolean isPrime(long l){
return BigInteger.valueOf(l).isProbablePrime(1);
}

}