我必須找到小於或等於SQUARE_ROOT(N)
的最大數字,並且除以N
。
最直接的解決是O(SQUARE_ROOT(N)),是否有任何O(logN)的解決方案,因爲數量可以變化。在的10^18的範圍大。查找除以的高度數N
0
A
回答
-1
如果N複合,然後
N = MaximumDivisor(N) * MinimumDivisor(N).
1
如果N
等於p*q
,其中p
和q
是質數,你會發現這個素數的第一個回答你的問題。所以這個問題一般不會比Integer factorization容易。並且沒有已知的O(logN)複雜度算法。
沒有公佈可以在多項式時間中因式分解所有整數的算法,即可以在時間O(b^k)中對某個常數k計算b位數。這種算法的存在和不存在都沒有被證明,但通常懷疑它們不存在,因此問題不在於P類。問題顯然在NP類中,但尚未證明是或不是NP完整的。一般認爲它不是NP完全的。
可能是你能找到不同的東西factorization algorithms中非常有用。
相關問題
- 1. 找N!除以n^2
- 2. 查找n位數的子序列數,可以被8整除
- 3. 查找可以被a或b整除的第N個數字
- 4. 查找二叉查找樹的高度
- 5. 查找地圖中最高的n值
- 6. 查找圖片的高度
- 7. 查找樹的高度
- 8. 查找素數高達X - 複雜度
- 9. 查找二叉樹高度
- 10. 查找整頁高度
- 11. 查找(X,Y)數據以高精度在Python
- 12. 查找5列數據幀的最高閾值以獲得n條記錄
- 13. 是否有快速查找if(n-1)的方法!可以被n整除?
- 14. Carrierwave和mini_magick查找寬度和高度
- 15. 查找以'n'開頭的用戶名
- 16. Prolog查找N個素數
- 17. 如何在UITableViewcell中查找特定單元高度的高度?
- 18. 提高刪除查詢的速度,刪除大量數據?
- 19. 找到除數和他們的除數等以一定深度
- 20. 查找大n(十進制表示精度)的組合數C(n,r)
- 21. 使用jquery查找類的高度
- 22. 從iFrame內部查找div的高度
- 23. 返回二叉查找樹的高度
- 24. 查找非二叉樹的高度
- 25. 查找TextLayout組件的文本高度
- 26. 查找滾動div的底部高度?
- 27. 查找多路樹的高度
- 28. 查找父視圖的高度
- 29. 查找行間距的高度
- 30. WebBrowser - 查找渲染文本的高度
那麼如何找到MaximimDivisor(N)這是重點? –
找到最小的除數... –
@ChristoferOhlsson如何找到O(lg N)中的最小除數?從邏輯上講,如果我能找到最小的除數,我可以在O(1)中找到最大的除數,所以對我來說它們是相同的問題 – shole