日にちの素因数分解
x 月 y 日を z = 100 * x + y と表現したとき、z の約数の個数が最も多くなるような x と y を求めよ。
この問題を解いてくれた物理の後輩に感謝。答えはふたつあるそうです。
勘で解いたら間違えていたよ．仕方がないのでまたもコンピュータを使ったよ．最後に出力とソースを載せておくから暇な人は見るがいいよ．でも
static boolean ifPrime(int n){ // n<37
switch(n){
case 2:case 3:case 5:case 7:case 11:case 13:case 17:case 19:
case 23:case 29:case 31: return true;
default: return false;
}
}これはひどいと自分でも思う．だけどさ，ここで
for(int i=2;i<=Math.sqrt(n);i++) if(n%i==0) return false; return true;
とかやるの無駄だし．11 個しかないんだからリスト作っちゃえばいいじゃん．
ということで暇人用にリンク & コピペ．暇で Java コンパイラ持ってる人は自己責任で実行してみるもよいよ．
http://melvy.hp.infoseek.co.jp/misc/CalendarMeasure_result.txt
http://melvy.hp.infoseek.co.jp/misc/CalendarMeasure.java
| 1 2 3 4 5 6 7 8 9 10 11 12 ---+------------------------------------ 1 | 2 4 4 2 4 2 2 6 4 8 4 2 2 | 8 4 4 8 4 8 16 4 8 8 8 4 3 | 2 4 4 4 2 6 4 4 8 4 2 4 4 | 8 12 10 6 24 6 14 12 8 6 20 12 5 | 8 4 4 10 4 6 8 8 4 8 8 4 6 | 4 4 12 8 8 8 4 8 8 4 8 12 7 | 2 6 2 4 6 2 4 4 2 4 8 4 8 | 12 10 12 16 6 12 12 8 6 30 6 8 9 | 2 4 4 2 2 8 2 2 6 2 2 8 10 | 8 16 8 8 16 8 8 20 16 8 16 12 11 | 4 2 2 4 4 4 6 2 2 4 4 4 12 | 10 6 16 6 10 18 8 12 20 12 8 12 13 | 2 4 2 4 8 2 4 4 4 2 8 2 14 | 8 4 4 12 4 4 16 8 4 12 4 4 15 | 4 4 12 4 4 8 8 4 8 8 4 12 16 | 6 16 6 12 12 16 6 20 6 8 18 14 17 | 6 4 2 4 4 2 4 4 4 6 2 2 18 | 4 4 8 8 8 8 4 4 16 4 8 16 19 | 4 4 4 2 4 2 2 12 2 2 4 4 20 | 16 12 14 24 16 12 30 12 16 24 24 12 21 | 3 4 4 2 2 8 4 2 4 2 4 8 22 | 4 8 8 4 12 4 6 8 4 8 16 8 23 | 4 2 4 6 2 4 4 2 4 8 2 2 24 | 6 12 15 8 6 20 6 8 24 11 6 24 25 | 4 9 6 6 12 5 6 12 6 6 12 9 26 | 12 4 4 8 4 4 12 8 4 16 4 4 27 | 2 2 4 4 4 8 2 2 6 4 6 4 28 | 8 12 8 6 20 6 16 18 12 6 16 6 29 | 4 2 4 8 3 4 7 2 2 8 2 2 30 | 8 16 8 8 24 8 8 16 8 8 16 31 | 2 2 6 4 4 2 2
class CalendarMeasure{
public static void main(String args[]){
int x,y,i,j,tmp,nm;
System.out.println(" | 1 2 3 4 5 6 7 8 9 10 11 12");
System.out.println("---+------------------------------------");
for(y=1;y<=31;y++){
if(y<10) System.out.print(" "+y+" |");
else System.out.print(y+" |");
for(x=1;x<=12;x++){
tmp = x*100+y;
nm = 1;
for(i=2;i<=Math.sqrt(tmp);i++){
if(ifPrime(i)){
for(j=1;;j++){
if(tmp%i==0) tmp /= i;
else break;
}
nm *= j;
}
}
if(tmp!=1) nm *= 2;
if(y>maxDay(x)) System.out.print(" ");
else if(nm<10) System.out.print(" "+nm);
else System.out.print(" "+nm);
}
System.out.println();
}
}
static int maxDay(int n){
switch(n){
case 1:case 3:case 5:case 7:case 8:case 10:case 12: return 31;
case 4:case 6:case 9:case 11: return 30;
case 2: return 29;
default: return -1;
}
}
static boolean ifPrime(int n){ // n<37
switch(n){
case 2:case 3:case 5:case 7:case 11:case 13:case 17:case 19:
case 23:case 29:case 31: return true;
default: return false;
}
}
}載せてみたらほんとに無駄だった．
