问题及解答

方法一：

使用传统的方法判断, 即对于 $N > 3$, 用 $i=1,3,\ldots, [\sqrt{N}]$ 去试除 $N$, 如果都无法除尽, 则 $N$ 是素数.

不过当 $N$ 很大时, 这个算法效率很低下.

方法二：

首先将前 1000 个或 1,000,000 个素数读入内存, 采用二叉查找树的结构.

利用查找方式判定一个整数(在此范围内)是否是素数.

[评论] 这个需要预先得到这 1,000,000 个素数. 即使不考虑这部分所耗的时间, 后续使用二叉查找树, 查找 $N$ 是否在其中也需要花费 $\log_2 N$ 的时间(指时间复杂度).