我試圖找到檢查給定數字是否為素數的最快方法（在Java中）。以下是我提出的幾種素性測試方法。有沒有比第二個實現更好的方法（isPrime2）？ public class Prime { public static boolean isPrime1(int n) { if (n <= 1) { return false; } if (n == 2) { return true; } for (int i = 2; i <= Math.sqrt(n) + 1; i++) { if (n % i == 0) { return false; } } return true; } public static boolean isPrime2(int n) { if (n <= 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) { if (n % i == 0) { return false; } } return true; } }public class PrimeTest { public PrimeTest() { } @Test public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException { Prime prime = new Prime(); TreeMap<Long, String> methodMap = new TreeMap<Long, String>(); for (Method method : Prime.class.getDeclaredMethods()) { long startTime = System.currentTimeMillis(); int primeCount = 0; for (int i = 0; i < 1000000; i++) { if ((Boolean) method.invoke(prime, i)) { primeCount++; } } long endTime = System.currentTimeMillis(); Assert.assertEquals(method.getName() + " failed ", 78498, primeCount); methodMap.put(endTime - startTime, method.getName()); } for (Entry<Long, String> entry : methodMap.entrySet()) { System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds "); } }}
3 回答
慕容森
TA貢獻1853條經驗 獲得超18個贊
你邁出了消除2的所有倍數的第一步。
但是，你為什么要止步呢？你可以消除所有3的倍數，除了3，所有5的倍數除了5，等等。
當你按照這個推理得出結論時，你會得到Eratosthenes的篩子。
添加回答
舉報
0/150
提交
取消