查找除以的高度數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）複雜度算法。

沒有公佈可以在多項式時間中因式分解所有整數的算法，即可以在時間O（b^k）中對某個常數k計算b位數。這種算法的存在和不存在都沒有被證明，但通常懷疑它們不存在，因此問題不在於P類。問題顯然在NP類中，但尚未證明是或不是NP完整的。一般認爲它不是NP完全的。

可能是你能找到不同的東西factorization algorithms中非常有用。