找到一个大小的互质数

我有一个任意数x。我想计算一个与x相近的数字，它与x的平方根很接近（ish）。我不需要全部找到它们，并且因子x是昂贵的。我只需要一个号码。找到一个大小的互质数

恒定时间，最好。

2017-09-15 Scott

选择一个素数，它不会将x关闭（ish）到根x？ – dmuir

计算素数是昂贵的... – Scott

...有很多他们......除非他们是“特殊”素数。梅森素数太稀少，有像log（x）那样的东西比x小。然而，如果有一类素数的根（x）小于x，很好地分布，封闭形式来寻找，那将是理想的。我希望得到这样的解决方案...欧几里德算法是log（x），我不知道任意数的副本的分布情况，但是素数的分布是这样的，以至于在根（x）附近找到一个素数在>> log（x）... log（x）^ 2我想。 – Scott

您可以用Euclidean algorithm相当有效地计算GCD，所以如果您只是尝试接近平方根的数字，您应该很快找到候选人。

你不可能得到一串有共同因素的数字，因为如果你找到一个普通的素数p，下一次你可以用相同的素数命中p后。

来源

2017-09-15 21:20:28

找到一个大小的互质数

回答

相关问题