首先一个最大的改进,for (long i = 3; i < num; i = i + 2)-->long sqrtNum = (long)(Math.sqrt(num) + 1)for (long i = 3; i < sqrtNum; i = i + 2)
就可以了,检查一个数A是否是质数,只要从3往上+2看能否整除,直到这个的平方根因为如果一直到Sqrt(A)一直没有能整除的话,检查超过Sqrt的部分也是没有必要的,那个肯定是个质数。这样改进之后的算法复杂度,降低很多
就可以了,检查一个数A是否是质数,只要从3往上+2看能否整除,直到这个的平方根因为如果一直到Sqrt(A)一直没有能整除的话,检查超过Sqrt的部分也是没有必要的,那个肯定是个质数。这样改进之后的算法复杂度,降低很多
使用原来的算法寻找1~50000内的质数,耗时6.4秒。
使用平方根算法寻找1~50000内的质数,耗时0.28秒。以下是新算法的代码:
while (endValue < 0 || num < endValue)
{
//平方根算法
long sqrtNum = (long) (Math.sqrt(num) + 1);
inner:for (long i = 3; i <= sqrtNum; i = i + 2)
{ if (num % i == 0)
{
break inner;
}
else if (i == sqrtNum||i==sqrtNum -1)
{
System.out.println(num);
}
}
//只计算奇数
num = num + 2; //去除尾数为5的数
if (num % 5 == 0)
{
continue;
}
}
----------------------------
另外,你提出的后一种算法我没试过。不过我觉得如果那样算的话,则还需要计算SQRT(A)以内的质数,可能反而增加了运算时间。
public static void main(String[] args){
int begin = Integer.parseInt(args[0]);
int end = Integer.parseInt(args[1]);
long l1 = System.currentTimeMillis();
boolean flag[] = new boolean[++end];
flag[0] = flag[1] = flag[2] = true;
int limit = (int)Math.sqrt(end);
for (int j=3; j<=limit; j+=2){
if (flag[j] == false){
for (int i=j+j; i<end; i+=j){
flag[i] = true;
}
}
}
System.out.println("Used:"+(System.currentTimeMillis()-l1));
/*
System.out
.println("Prime Numbers from " + begin + " to " + (end-1) + ":");
if(begin%2 == 0)begin++;
for(int i=begin; i<end; i+=2){
if(flag[i] == false){
System.out.print(i + ",");
}
}*/
}
}
比如,你现在的上限args[1] = 50000,也就是SQRT(A) = 224,大致相当于你要尝试112个奇数,而224以内的质数显然只有几十个。而每一个num你都能节省那么多次计算,何乐而不为呢?而且,这个args[1]越大,有时越明显。当然如果args[1]过小的话,比如 < 1000的话,可能没有直接从args[0]开始计算来的快。所以,可能需要添加一个判断,什么范围用质数的查找,什么时候,直接从3开始+2另外,如果偷懒一点,把所有100以内的质数作为已知条件的话,速度更快(但不明显)。
把已经运算出来的质数存储起来,用作除数来判断新的质数。这个算法应该很快,但略有点复杂。等我写出程序再贴出来。先贴出使用平方根算法结果:Search prime ranged from 1 to 10000000 cost time: 105.852 second(s)
primes.add(new Long(3));while (endValue < 0 || num < endValue)
{
long sqrtNum = (long) (Math.sqrt(num) + 1);
boolean foundPrime=false;
inner:for (Iterator iter=primes.iterator();iter.hasNext();)
{
long i=((Long)iter.next()).longValue(); if (num % i == 0||i>sqrtNum)
{
break inner;
}
else if (i == sqrtNum||i==sqrtNum -1)
{
foundPrime=true;
System.out.println(num);
}
}
if(foundPrime){
primes.add(new Long(num));
foundPrime=false;
}
//只计算奇数
num = num + 2; //去除尾数为5的数
if (num % 5 == 0)
{
continue;
}
}结果:
Search prime ranged from 5 to 10000000 cost time: 46.346 second(s)快了很多。但是有个bug,运算到8468077就停止了,没有继续查找剩余质数。不知道程序中有什么缺陷。
boolean isPrime;
for (int i=(startValue%2==0)?startValue+1:startValue; i<=endValue; i+=2) {
if (i%5 ==0) {
continue;
}
isPrime = true;
sqrtValue = Math.sqrt(i) + 1;
for (int j=3; j<=sqrtValue; j++) {
if (i%j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println(i + " is prime.");
}
}
if (num % 5 == 0) {
continue;
}这句应该放到刚进入 while 的地方
放到底下不紧啥用没有, 而且还增加一定开销
本来看到一开始的程序就想回平方根的做法
不过一楼看来很快,到二楼基本上就补充完整了说一些我的看法,大质数的算法是一个世界性的难题。至今(包括我所看到的研究)应该说都是递推算法。也就是说必须要知道前面的质数才能判断后面那个是不是质数。我所能看到的最好的算法是不必一个个的递推,而是知道前几个可以跳过几个知道后面那个是不是质数。
shine333(enihs) 的回答很正确,个人认为这个问题并不是一个算法问题,而是一个数学问题。ps:应该用数组来做
long[] elements; int count; public LongList() {
this(10);
} public LongList(int initCapacity) {
elements = new long[initCapacity];
} public int size() {
return count;
} public void add(long value) {
if (count >= elements.length) {
long[] newElements = new long[elements.length << 1];
System.arraycopy(elements, 0, newElements, 0, count);
elements = newElements;
} elements[count++] = value;
} public LongIterator iterator() {
return new LongIterator() {
int index; public boolean hasNext() {
return index < count;
} public long next() {
return elements[index++];
}
};
}
} static interface LongIterator {
boolean hasNext(); long next();
} public static LongList seekPrime(long maxValue) {
LongList primeList = new LongList( (int) (maxValue >> 4) + 10); primeList.add(2); for (long num = 3; num <= maxValue; num += 2) { //Square root
long sqrt = (long) (Math.sqrt(num) + 1); boolean isPrime = true; for (LongIterator iter = primeList.iterator(); iter.hasNext(); ) {
long div = iter.next(); if (div >= sqrt) {
//This is a prime
continue;
} if (num % div == 0) {
//Not a prime
isPrime = false;
break;
}
} if (isPrime) {
primeList.add(num);
} } return primeList;
} public static void main(String[] args) {
long maxValue = Long.parseLong(args[0]); long startTime = System.currentTimeMillis(); LongList primeList = seekPrime(maxValue); long endTime = System.currentTimeMillis(); System.out.println("Time Cost: " + (endTime - startTime) + "ms"); System.out.println("Total Found: " + primeList.size()); }
}这里的改进,在算法上没什么改进随便跑了几遍,发现用直接存放long的容器,比存放Long的java.util.Collection快很多,而且发现一个的规律,质数的个数,大致是maxValue的1/10不到一点,所以,我的初始容器大小,定在了maxValue的1/16左右,省得多次的内存分配,当然,在运行的时候,指定了-Xms -Xmx参数。另外,我还没有试过1000000以上的数字。另外,我曾尝试了类似双向冒泡排序的算法,将maxValue也逐步往下减,但发现效果并不好。
import java.io.IOException;
import java.io.InputStreamReader;public class PrimeExplorer {
public static void main(String[] args) throws IOException {
int startValue;
int endValue;
int n;
int sqrt;
int divisor;
int count;
Prime head;
Prime tail;
Prime prime;
boolean isPrime;
BufferedReader in;
in = new BufferedReader(new InputStreamReader(System.in)); // Get input.
do {
try {
System.out.print("From: ");
startValue = Integer.parseInt(in.readLine());
System.out.print("To: ");
endValue = Integer.parseInt(in.readLine());
// Start from 11.
if (startValue < 11 || endValue <= startValue) {
continue;
} else {
break;
}
} catch (NumberFormatException e) {
continue;
}
} while (true); n = startValue;
// Start from even.
if (n % 2 == 0) {
n++;
}
count = 0; // Prepare all prime numbers in 10 except 1.
head = new Prime(5);
head.next = new Prime(3);
head.next.next = new Prime(7);
prime = head;
tail = head.next.next; //========================================
long startTime = System.currentTimeMillis(); for (isPrime = true; n < endValue;
n += 2, prime = head, isPrime = true) { sqrt = (int) Math.sqrt(n) + 1; // Find prime number.
for (divisor = prime.value; prime.next != null;
prime = prime.next, divisor = prime.value) {
if (n % divisor == 0) {
isPrime = false;
break;
} else if (divisor > sqrt) {
break;
}
} // Append this prime number to the list tail.
if (isPrime) {
count++;
prime = tail;
prime.next = new Prime(n);
tail = prime.next;
// TODO: Uncommont this for validating result.
//System.out.println(n);
}
} System.out.println("Total: " + count);
long endTime = System.currentTimeMillis();
System.out.println("cost: " + (endTime - startTime));
//========================================
} private static class Prime {
public Prime next = null;
public int value; public Prime(int value) {
this.value = value;
}
}
}平方根是个好方法
存储质数更是个好方法
但是使用数组存储质数在这里显然就不是一个好方法了
这里使用链表比较合适, 即节省空间, 而且速度更快if (div >= sqrt) {
//This is a prime
continue;
}
shine333兄的问题出在这块语句
这里就算找到了质数,还是要遍历完整个数组
虽然数组里面都是质数, 数大了也受不了
相比线性探测法性能优势较弱而链表法一可最小化使用内存资源占用,
二可客服此缺陷, 当确定 n 不是质数后立刻跳出循环
从而大大提升性能, 达到存储质数法的目的从 11 算到 10,000,000
"开方法"耗时 70秒 左右
"开方法 + 链表存储质数法"耗时 9秒 左右
机器是 Athlon 2500+; 1G DDR333 RAM
个人感觉这里没有使用 long 的必要
因为 2,000,000,000 以上的数大可交给 64bit CPU 去计算
使用 32bit CPU 计算 long 在性能上是很难令人接受的
讲上面程序里面的 int 换成 long 以后
从 11 算到 10,000,000 耗时 22秒 多
性能粗略的算是降低了整一倍
以上测试均使用官方SDK
虽然不论是 int 还是 long 在算法上没区别
但是使用 long 的测试过程是在令人太难忍受了...顺便纠正上面一个错误
"开方法"耗时 70秒 左右
这个程序当时使用的是 long
换成 int 后结果变为 27秒 左右开方法:
From: 11
To: 10000000
Total: 664575
cost: 27109开方法 + 链表存储质数法:
From: 11
To: 10000000
Total: 664575
cost: 9516
然后在翻译为java 再做优化
check x isPrime?
endisPrime?的算法复杂度是O(n*n),这是不用讨论的,否则RSA加密就已经没有意义了。这样一来,“求n以内的所有素数”整个算法的复杂度就是O(n*n*n)。那么,O(n*n*n)是否最低的近似算法复杂度?在做那些细节优化之前不妨先考虑这个问题。我再给个提示:答案早在两千多年前就已经有了。
还望 Schlemiel(维特根斯坦的扇子) 将这两千年前的答案赐教于我等
foreach x = 2 to sqrt(n)
m = 2
while x*m <= n
container.remove(x*m)
m++
end
end先设P=2,将n以内P的所有倍数划去;再设P=3,将n以内P的所有倍数划去;如此反复直至P大于n的平方根。划剩下来的就是n以内所有的素数。这个算法的复杂度是O(n*n)。连寻找素数的基本算法是什么都没想清楚就开始写程序,真是不怕累。
check x isPrime?
end这个是符合我们现在讨论的算法的,而你说的 isPrime?是O(n*n),就好像不对了我们现在是foreach x from 2 to n
foreach y from 2 to min(maxKnownPrime, SQRT(x))
if (x mod y == 0) Not Prime, quit loop
end
end仍然是O(n*n)吗
下面的程序是按照 Schlemiel(维特根斯坦的扇子) 老兄的算法做的实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class PrimeFilter {
public static void main(String[] args) throws IOException {
int startValue;
int endValue;
int count;
int limit;
int factor;
Candidate head;
Candidate prime;
Candidate candidate;
BufferedReader in;
boolean print = false;
// Get input.
in = new BufferedReader(new InputStreamReader(System.in));
do {
try {
System.out.print("From: ");
startValue = Integer.parseInt(in.readLine());
System.out.print("To: ");
endValue = Integer.parseInt(in.readLine());
break;
} catch (NumberFormatException e) {
continue;
}
} while (true);
//========================================
long startTime = System.currentTimeMillis(); // Generate candidates.
head = new Candidate(3);
candidate = head;
// Add odd only.
for (int i = 5; i < endValue; i += 2) {
candidate.next = new Candidate(i);
candidate = candidate.next;
} // Filter prime numbers.
limit = (int) Math.sqrt(endValue) + 1;
for (prime = head, count = endValue / 2;
prime.value < limit; prime = prime.next) {
for (factor = prime.value, candidate = prime;
candidate != null && candidate.next != null;
candidate = candidate.next) {
if (candidate.next.value % factor == 0) {
count--;
candidate.delNext();
}
}
} if (print) {
for (prime = head; prime.next != null; prime = prime.next) {
System.out.println(prime.value);
}
} System.out.println("Total: " + count);
long endTime = System.currentTimeMillis();
System.out.println("Cost: " + (endTime - startTime) + "ms");
//======================================== } private static class Candidate {
public Candidate next;
public int value; public Candidate(int value) {
this.value = value;
} public void delNext() {
next = next.next;
}
}
}运行结果如下:
java -Xms200m -Xmx300m PrimeFilter
From: 3
To: 10000000
Total: 664579
Cost: 45156ms实在想不通是哪儿出问题了...
我的机器配置:xp(sp4)/PIII 1G/512M11到10000000,一共15秒,找到664575个质数。有点差别的地方是,使用了ArrayList,而且在存储已知质数的list中,使用了for循环而不是foreach循环(提高了12秒左右,原来是27秒)
public static void main(String[] args) throws Throwable { long start = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
int x = i % (i + 100);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
}}试了三次,分别耗时4336ms,4587ms,4437ms而使用int x = i * (i + 100); 仅耗时681ms,641ms,651ms。
我想学习一下怎么实现的
primes[i] = i + 2;
}int sqrt = (int) (Math.sqrt(maxValue) + 1);for (int i = 2; i < sqrt; i++) {
int m = 2;
while (i * m <= maxValue) {
primes[i * m - 2] = 0;
m++;
}
}基本上就是这样子,没有仔细检查是否是该算法的正确表述。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class PrimeFilter {
public static void main(String[] args) throws IOException {
int startValue;
int endValue;
int total;
int limit;
int prime;
int factor;
int product;
int n;
int[] list;
BufferedReader in;
// Get input.
in = new BufferedReader(new InputStreamReader(System.in));
do {
try {
System.out.print("From: ");
startValue = Integer.parseInt(in.readLine());
System.out.print("To: ");
endValue = Integer.parseInt(in.readLine());
break;
} catch (NumberFormatException e) {
continue;
}
} while (true); //========================================
long startTime = System.currentTimeMillis(); n = endValue;
list = new int[n];
list[0] = 0;
list[1] = 1;
list[2] = 2;
total = 2;
for (int i = 3; i < n; i += 2) {
total++;
list[i] = i;
} limit = (int) Math.sqrt(n) + 1;
for (prime = 3; prime < limit;) {
// Filter non prime number.
for (factor = prime; (product = factor * prime) < n; factor += 2) {
if (list[product] != 0) {
list[product] = 0;
total--;
}
}
// Skip non prime number.
do {
prime += 2;
} while (list[prime] == 0);
} // TODO: Change this flag for validating result.
if (false) {
System.out.println(list[1] + "\n" + list[2]);
for (int i = 3; i < list.length; i += 2) {
if (list[i] != 0) {
System.out.println(list[i]);
}
}
} System.out.println("Total: " + total);
long endTime = System.currentTimeMillis();
System.out.println("Cost: " + (endTime - startTime) + "ms");
//========================================
}
}我实现了一下
的确是有了质的飞跃
上面的实现可能还有可优化的地方
我们上面的算法关键问题不在 % 运算(虽然也有一定影响)
而是在开方上面
之前的算法要开方 n/2 次
而这个算法只要开一次
不过这个算法太耗费资源, 算到 2 ^ 31 需要 2G 内存
无论如何这个算法的确是非常快