No.237 作図可能性
evima問題文最終更新日: 2015-11-14 17:47:23
問題文
整数 $A$ が与えられます。 $3$ 以上 $A$ 以下の整数 $n$ のうち、定規とコンパスによって正 $n$ 角形が作図可能であるようなものの個数を求めてください。
定規とコンパスによる作図、およびこの問題を解く上で必要な知識に関しては Wikipedia を参照してください： http://ja.wikipedia.org/wiki/定規とコンパスによる作図
入力
$A$
- $3 \le A \le 10^9$
出力
条件を満たす整数 $n$ の個数を出力し、末尾で改行せよ。
サンプル
サンプル1
入力
9
出力
5
正三角形、正四角形、正五角形、正六角形、正八角形はいずれも定規とコンパスにより作図可能ですが、正七角形と正九角形は作図不可能です。
サンプル2
入力
1000000000
出力
456
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。