分割する高さの数字を見つけるN

Question

SQUARE_ROOT(N)以下の最大数を見つけなければならず、Nを割ります。

最も直接的な解決策は、O（をsquare_root（N））であり、数のである任意O（logN個）溶液を10^18の範囲で大きな変化させることができます。

Answer 1

Nが複合体である場合には、

N = MaximumDivisor(N) * MinimumDivisor(N). 

Answer 2

Nがpとqが素数p*qに等しい場合、あなたはこれがあなたの質問に答えるために最初の素数を見つける必要があります。だからこの問題は一般的にInteger factorizationより簡単ではありません。また、O（logN）の複雑さを持つ既知のアルゴリズムはありません。

なしアルゴリズムはいくつかの定数kのタイムO中のBビット数（B^k）を考慮することができること、すなわち、多項式時間ですべての整数を因数分解することができ、その公開されていません。このようなアルゴリズムの存在または非存在は証明されていないが、一般的にそれらは存在しないと疑われ、そのため問題はクラスPにはない。この問題は明らかにNPクラスにあるが、 NP完全ではない。それは一般的にNP完全ではないと思われる。

factorization algorithmsの中で有用なものが見つかるかもしれません。