#P0821. 伪质数

伪质数

题目描述

怎么到现在了还有人连判断质数都不会的?

在大于等于22的整数中,只有11和他本身两个因子的数被称为质数。

现在把条件放宽一点:在此题中,对于一个大于等于22的整数nn,如果其因子数量小于等于⌈lg⁡n⌉\lceil \lg n \rceil,那么我们称他为伪质数。

现在,队长给了你nn个正整数,请找出其中所有的伪质数,并从小到大输出出来。

  • ⌈n⌉\lceil n \rceil表示nn向上取整,如⌈3.14⌉=4\lceil 3.14 \rceil = 4。

输入格式

第一行输入一个整数n(1≤n≤1000)n(1 \le n \le 1000)。

第二场输入nn个整数a1,a2,...,an(1≤ai≤109)a_1, a_2, ..., a_n(1 \le a_i \le 10^9)。

题目保证:nn个数中至少有一个伪质数。

输出格式

从小到大输出所有的伪质数,每两个数之间用空格隔开。

样例

3
7 17 107
17 107

提示

lg⁡\lg在C语言的math.hmath.h库中为log10()。