分享几个素数算法。。。
如题，分享几个自己精心收集并改进的素数算法：
public class PrimeTool
{
/**
* 判断是否为素数
*
* @param number
* @return
*/
public static boolean isPrime(int number)
{
if (number < 2)
return false;
if (number == 2)
return true;
if (number % 2 == 0)
return false;
for (int i = 3, j = (int) Math.sqrt(number); i <= j; i += 2)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
/**
* 获取不大于number的所有素数
*
* @param number
* @return int数组
*/
public static int[] makePrimes3(int number)
{
if (number < 2)
return null;
if (number == 2)
return new int[] { 2 };
if (number == 3)
return new int[] { 2, 3 };
int[] primes = new int[number / 2 + 1];
primes[0] = 2;
primes[1] = 3;
primes[2] = 5;
int cnt = 3;
for (int i = 7; i <= number; ++i)
{
if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0)
{
continue;
}
if (isPrime(i))
{
primes[cnt++] = i;
}
}
int[] array = new int[cnt];
System.arraycopy(primes, 0, array, 0, cnt);
return array;
}
/**
* 构造素数序列primes[]
*
* 原理：线行筛选
*
* @param primes
* @param number
* @param flag
* true则返回所有不大于number的素数，false则返回前number个素数
* @return primes数组实际长度
*/
private static int makePrimesnumberber(int[] primes, int number,
boolean flag)
{
if (number < 2)
return 0;
primes[0] = 2;
if (number == 2)
return 1;
primes[1] = 3;
boolean isPrimes;
int i, j, cnt;
for (i = 5, cnt = 2; (flag ? i : cnt) < number; i += 2) //基本类型无法引用，不知道有没有更好地实现
{
isPrimes = true;
for (j = 1; primes[j] * primes[j] <= i; ++j)
{
if (i % primes[j] == 0)
{
isPrimes = false;
break;
}
}
if (isPrimes)
primes[cnt++] = i;
}
return cnt;
}
/**
* 获取不大于number的所有素数
*
* @param number
* @return int数组
*/
public static int[] makePrimes2(int number)
{
int[] primes = new int[number / 2 + 1];
int total = makePrimesnumberber(primes, number, true);
int[] array = new int[total];
System.arraycopy(primes, 0, array, 0, total);
return array;
}
/**
* 获取前number个素数
*
* @param number
* @return int数组
*/
public static int[] makeNumPrimes(int number)
{
int[] primes = new int[number];
int total = makePrimesnumberber(primes, number, false);
int[] array = new int[total];
System.arraycopy(primes, 0, array, 0, total);
return array;
}
/**
* 获取不大于number的所有素数
*
* 原理： 能被素数整除的则为非素数（排除能被2,3,5,7,11...整除的数，最后只剩下素数） 数组序号： 0 1 2 3 4 5 6 7
* 8... *2+1 即可得到代表的数值 isPrime代表奇数数组： 1 3 5 7 9 10 11 13 15...
* //若被确认为非素数，则标示为false linkNext代表连接顺序：1 2 3 4 5 6 7 8 9...
* //指向下一个未被标示为false的数
*
* @param number
* @return int数组
*/
public static int[] makePrimes(int number)
{
int primeSize = number / 2 + (number % 2 == 0 ? 0 : 1);
boolean[] isPrime = new boolean[primeSize]; // 直接排除能被2整除的数
for (int i = 0; i < primeSize; i++)
{
isPrime[i] = true;
}
int linkSize = number / 6 + 2; // 去掉能被2和3整除的数
int[] linkNext = new int[linkSize];
for (int i = 0; i < linkSize; i++)
{
linkNext[i] = i + 1;
}
int total = primeSize;// 统计未被排除的数，最后即为素数个数
int primeNumber = 3; // 用来被整除的素数，从3开始
int multiplier; // 乘子，与primeNumber相乘即可获得要排除的数，>=primeNumber
int result, index, next;
while (primeNumber * primeNumber <= number)
{
multiplier = primeNumber;
result = multiplier * primeNumber;
while (result <= number)
{
isPrime[(result - 1) / 2] = false;
--total;
index = (multiplier - 1) / 2;
next = linkNext[index];
if (isPrime[next] == false)
linkNext[index] = linkNext[next];
multiplier = next * 2 + 1;
result = multiplier * primeNumber;
}
primeNumber = linkNext[(primeNumber - 1) / 2] * 2 + 1; // 下一个素数
}
int[] array = new int[total];
int cnt = 0;
array[cnt++] = 2;
for (int i = 1; i < primeSize; i++)
{
if (isPrime[i])
{
array[cnt++] = (i * 2 + 1); // 恢复出素数
}
}
return array;
}
}
在本人电脑上测试输出1000000以内的素数，三个算法分别用时：
makePrimes ：29595327ns
makePrimes2：88697645ns
makePrimes3：180091190ns
欢迎大家分享各种高效算法^ ^
[解决办法]
把 makePrimesnumberber 优化了一下，更快一些。
private static int makePrimesnumberber(int[] primes, int number, boolean flag) { int cnt = 0; if (number < 2) { return cnt; } primes[cnt++] = 2; if (number == 2) { return cnt; } primes[cnt++] = 3; if (flag) { for (int i = 5; i < number; cnt += find(primes, i, cnt), i += 2); } else { for (int i = 5; cnt < number; cnt += find(primes, i, cnt), i += 2); } return cnt;}private static int find(int[] primes, int n, int count) { if (n % 3 == 0) { return 0; } for (int i = 1; primes[i] * primes[i] <= n; i++) { if (n % primes[i] == 0) { return 0; } } primes[count] = n; return 1;}
[解决办法]
测试某一个数是否为素数（合数）的 Miller-Rabin 算法，效率远比根号验证法快。
public class MillerRabin { public static void main(String[] args) { long t0, t1; t0 = System.nanoTime(); boolean b = !isComposite(479001599); boolean c = !isComposite(456789012); t1 = System.nanoTime(); System.out.println(t1 - t0); System.out.println(b + " " + c); } /** * <p>Miller-Rabin 测试某一个数是否是合数</p> * * @param n 需要测试的数 * @return true: 该数为合数；false: 该数为素数 */ public static boolean isComposite(int n) { if (n < 2) { throw new IllegalArgumentException("number must greater than or equals 2"); } // 排除 2、3、5、7 以加速测试 if (n == 2 || n == 3 || n == 5 || n == 7) { return false; } // 偶数 if ((n & 1) == 0) { return true; } // 排除 3、5、7 的倍数，以加速测试 if (n % 3 == 0) { return true; } if (n % 5 == 0) { return true; } if (n % 7 == 0) { return true; } // 寻找 s 和 d 以满足 n = 2^s * d + 1 int s = 0, d = n - 1; while ((d & 1) == 0) { d >>= 1; s++; } // 对于各种数值需要进行 Miller-Rabin 基准测试的素数值 // 参考：http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test // if n < 1,373,653, it is enough to test a = 2 and 3; // if n < 9,080,191, it is enough to test a = 31 and 73; // if n < 4,759,123,141, it is enough to test a = 2, 7, and 61; // if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11; // if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13; // if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17. if (n < 1373653) { if (loopMillerRabin(s, d, n, 2, 3)) { return true; } } else if (n < 9080191) { if (loopMillerRabin(s, d, n, 31, 73)) { return true; } } else { // 4,759,123,141 已经超过 int 的最大值，因此大于等于 9080191 就采用 4,759,123,141 的基准测试 if (loopMillerRabin(s, d, n, 2, 7, 61)) { return true; } } return false; } /** * <p>循环 Miller-Rabin 测试</p> * * @param s n = 2^s * d + 1 中的 s 值 * @param d n = 2^s * d + 1 中的 d 值 * @param n 需要测试的数 * @param t 测试的基准素数 */ private static boolean loopMillerRabin(int s, int d, int n, int... t) { for (int i = 0; i < t.length; i++) { if (testMillerRabin(t[i], s, d, n)) { return true; } } return false; } /** * <p>Miller-Rabin 基本测试</p> * * @param a 素性测试基准素数 * @param s n = 2^s * d + 1 中的 s 值 * @param d n = 2^s * d + 1 中的 d 值 * @param n 需要测试的数 * @return 测试某一数是否是合数。true: 该数是合数；false: 该数可能是素数。若返回 false * 需要进行多基准的联合测试才能判断该数确实是素数 */ private static boolean testMillerRabin(int a, int s, int d, int n) { if (montgomery(a, d, n) != 1) { int e = 1; for (int i = 0; i < s; i++) { if (montgomery(a, d * e, n) + 1 == n) { return false; } e <<= 1; } return true; } return false; } /** * <p>使用 Montgomery 算法计算 (base ^ exp) % mod 的值。</p> * * <p>由于 Java 中 int 的运算速度远远大于 long 的运算速度，因此该算法需要改进！</p> * * @param base 基数 * @param exp 指数 * @param mod 模数 */ private static int montgomery(int base, int exp, int mod) { if (base > 46340 || mod > 46340) { long temp = 1; long prod = base % mod; while (exp > 1) { if ((exp & 1) != 0) { temp = (temp * prod) % mod; } prod = (prod * prod) % mod; exp >>= 1; } return (int) ((temp * prod) % mod); } else { int temp = 1; int prod = base % mod; while (exp > 1) { if ((exp & 1) != 0) { temp = (temp * prod) % mod; } prod = (prod * prod) % mod; exp >>= 1; } return (temp * prod) % mod; } } /** * <p> * 根据复化辛普生法则计算高斯 Li 函数。Li(x) 近似于素数个数函数 π(x) * </p> * * @param x 数值范围 * @return 该值以内的素数个数的估计值 */ private static double gaussLi(int x) { int n = x; double s = 2; double h = (x - s) / n; double a = f(s + h / 2); double b = 0; for (int k = 1; k < n; k++) { a += f(s + k * h + h / 2); b += f(s + k * h); } return (h / 6) * (f(s) + 4 * a + 2 * b + f(x)); } /** * <p> * Guass Li(x) 积分函数项 * </p> * * @param x * @return */ private static double f(double x) { return 1 / Math.log(x); }}