OJ 题目：隐藏的因子

题目描述

给定一个正整数 (n)。

我们定义一个数 (v)：

(v) 是所有能够整除 (n) 的 (2) 的整数次幂中最大的一个。

例如：

• 当 (n=12) 时，能够整除 (12) 的 (2) 的整数次幂有 (1,2,4)，所以 (v=4)；
• 当 (n=18) 时，能够整除 (18) 的 (2) 的整数次幂有 (1,2)，所以 (v=2)；
• 当 (n=7) 时，能够整除 (7) 的 (2) 的整数次幂只有 (1)，所以 (v=1)。

现在请你判断 (v) 是否为质数。

如果 (v) 是质数，输出：

质数

否则输出：

非质数

---

输入格式

输入一个正整数 (n)。

---

输出格式

如果 (v) 是质数，输出：

质数

否则输出：

非质数

---

输入样例 1

12

输出样例 1

非质数

样例解释 1

(12) 的二进制表示为：

1100

它能够被 (1,2,4) 整除，其中最大的 (2) 的整数次幂是：

$v=4$

而 (4) 不是质数，所以输出：

非质数

---

输入样例 2

18

输出样例 2

质数

样例解释 2

(18) 的二进制表示为：

10010

它能够被 (1,2) 整除，其中最大的 (2) 的整数次幂是：

$v=2$

而 (2) 是质数，所以输出：

质数

---

输入样例 3

7

输出样例 3

非质数

样例解释 3

(7) 是奇数，只能被 (1) 这个 (2) 的整数次幂整除。

所以：

$v=1$

而 (1) 不是质数，所以输出：

非质数

---

数据范围

$1 \le n \le 10^9$

---

例如：

(n)	二进制	lowbit(n)	是否质数	输出
7	111	1	否	非质数
8	1000	8
10	1010	2	是	质数
12	1100	4	否	非质数
18	10010	2	是	质数