我試圖找到檢查給定數(shù)字是否為素?cái)?shù)的最快方法（在Java中）。以下是我提出的幾種素性測(cè)試方法。有沒(méi)有比第二個(gè)實(shí)現(xiàn)更好的方法（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貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超18個(gè)贊
你邁出了消除2的所有倍數(shù)的第一步。
但是，你為什么要止步呢？你可以消除所有3的倍數(shù)，除了3，所有5的倍數(shù)除了5，等等。
當(dāng)你按照這個(gè)推理得出結(jié)論時(shí)，你會(huì)得到Eratosthenes的篩子。
添加回答
舉報(bào)
0/150
提交
取消