快速判断一个数字是否可以表示为两个素数的倍数？

Question

假设您有 10e4 个数字。每个数字不超过10e6。如果每个数字可以表示为两个素数的倍数，那么如何有效地检查它？

例子：15可以表示为3*5。6可以表示为2*3。但是8不能用两个素数表示。

Answer 1

如果可能的话您不需要知道素数：

您可以预先计算一个包含 10e6 个条目的布尔表，该表表示该数字是否可以表示为两个素数的倍数。

您可以在 O(1) 中查找每个数字。

创建表需要一些时间，但可以提前完成。