java循环i++vs i+=2
我一直在尝试一种高效的算法来寻找素数,作为我尝试的一部分,我一直在使用以下代码。我有一个想法,通过改变I+=2的激励来加速循环,但实际上,这个改变似乎给我的程序的运行时间增加了2秒。有谁能解释为什么会发生这种情况,因为循环似乎需要完成一半的工作才能完成
for(int i = answers.get(answers.size()-1)+2;i<n;i++) {
int bit = i%64;
int currentInt = i/64;
int isPrime = (primes[currentInt] >> bit) & 1;
if(isPrime == 1) {answers.add(i);}
}
完整代码如下:
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
public class Primes15 {
static Long start;
public static IntStream stream() {
int numbers = 15350808;
int n = 982451712;
List<Integer> answers = new ArrayList<>();
long[] inverseShifts = new long[64];
long temp = 1;
for(int i = 0; i < inverseShifts.length; i++) {
inverseShifts[i] = temp ^ -1;
temp = temp << 1;
}
long[] primes = new long[numbers+1];
primes[0] = -6148914691370734930L;
for(int i = 1;i<primes.length; i++) {
primes[i] = -6148914691370734934L;
}
System.out.println("Setup taken " + (System.currentTimeMillis() - start) + " millis");
start = System.currentTimeMillis();
for(int p =3; p*p <=n; p+=2) {
int bit = p%64;
int currentInt = p/64;
long isPrime = (primes[currentInt] >> bit) & 1;
if(isPrime == 1) {
answers.add(p);
int cPrimeSquared = p*p;
int change = (p==2)? p : p+p;
for(int i = cPrimeSquared; i <= n; i += change) {
int innerBit = i % 64;
int innerInt = i /64;
isPrime = (primes[innerInt] >> innerBit) & 1;
if(isPrime == 1) {
primes[innerInt] = primes[innerInt] & inverseShifts[innerBit];
}
}
}
System.out.println("finder took " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
for(int i = answers.get(answers.size()-1)+2; i<n; i++) {
int bit = i%64;
int currentInt = i/64;
long isPrime = (primes[currentInt] >> bit) & 1;
if(isPrime == 1) {answers.add(i);}
}
System.out.println("search took " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
return answers.stream().mapToInt(i->i);
}
public static void main(String[] args) {
start = System.currentTimeMillis();
stream();
Long finish = System.currentTimeMillis();
System.out.println("Time taken " + (finish - start) + " millis");
}
}
共 (0) 个答案