試し割り法

単純なだけあって、名前が色々あります。英語も含めて。

• brute force (でも何故か日本語で全探索とは言わない)
• Trial Division (試し割り法)

　原理も何も、ただただ2以上の整数で割ってみるだけです。

printf("%d=", n);
for( i = 2 ; i * i ≤ n ; i++ ) {
  for( e = 0 ; n % i == 0 ; e++ ) n /= i;
  if( e == 0 ) continue;
  printf("%d^%d*", i, e);
}
printf("%d\n", n);

　最後に n を出力しているのは i のループで行き着かない範囲に残った素因数を出力するためです。たまに最後の出力が1になることもありますが気にしないように。