58B - Coins

問題

バーランド国は新しい硬貨を作ろうと考えた。その硬貨は、それよりも安いすべての硬貨で割り切れるものでなくてはならない。一番高い硬貨の値が与えられるので、なるべく硬貨の数が多くなるように硬貨を構成せよ。

解法

1になるまで、割れる素数で割っていけば良い。

コード

int main(){
  int n;
  cin>>n;
  vector<int> ans;
  ans.push_back(n);
  while(n!=1){
    FOR(i,2,n+1){
      if(n % i == 0){
        n /= i;
        ans.push_back(n);
        break;
      }
    }
  }
  REP(i,ans.size()){
    cout<<ans[i];
    putchar((i==ans.size()-1)?'\n':' ');
  }
  return 0;
}