問題一覧 > 通常問題

No.237 Constructibility

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 215
作問者 : evima
お気に入りにしたユーザー ProblemId : 239 / 自分の提出
問題文最終更新日: 2026-06-25 03:43:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 113 (順位表) の他の問題:

Problem Statement

You are given an integer $A$. Find the number of integers $n$ between $3$ and $A$, inclusive, such that a regular $n$-gon can be constructed with a straightedge and compass.

For straightedge-and-compass construction and the knowledge needed to solve this problem, refer to Wikipedia: http://ja.wikipedia.org/wiki/定規とコンパスによる作図

Input

$A$

  • $3 \le A \le 10^9$

Output

Print the number of integers $n$ satisfying the condition, followed by a newline.

Sample

Sample 1
Input
9
Output
5

The regular triangle, square, regular pentagon, regular hexagon, and regular octagon can all be constructed with a straightedge and compass, but the regular heptagon and regular nonagon cannot.

Sample 2
Input
1000000000
Output
456

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。