※ 引述《runtime ()》之銘言： : 請問各位大大 : 判斷一個數是否為質數 能想到的最快速做法? : 常會用到判斷質數 : 一個一個去除 判斷是否可整除是最慢的作法 : 我有改良到 n/2 接著是 根號n 然後目前是 根號n 只求奇數 : 有什麼更快的做法嗎? 聽說可以 一路掃到尾 每次都用前面找到的質數去除 : 雖然沒試過 可是看起來複雜度蠻高的 http://mathworld.wolfram.com/PrimalityTest.html 方法有很多, 甚至有 deterministic 的方法已經能做到 polynomial time. 不過這些方法的原理都不是很容易, 實做上也有一定困難度. -- その乾いた哀愁の瞳に去來するものは何か？ 失ったもの 得たもの そして廣大なネットの狹間で彼が見たものとは？ 虛像と實存と記號の中に彼は今、何を想うのか？ ＜バトルプログラマーシラセ＞ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.109.224.64