for (int i = 2; i * i <= max; i++) {
In my testing it's slightly faster to take the square root of max
rather than multiplying i * i
on each iteration.
for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {
It's only a fraction of a millisecond but a noticeable difference.
for (int j = i; i * j <= max; j++) {
isPrimeArray[i * j] = false;
}
You could simplify this.
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
Then rather than doing two multiplications per iteration, you can do one addition. Of course a good optimizer would notice that both multiplications are the same and only do one.
I prefer names that do not include the type, so I'd just call it isPrime
.
if(isPrime) {
nthPrime++;
}
if(nthPrime == n) {
return index;
}
You compare nthPrime
and n
more often than necessary. You can just say
if (isPrime) {
nthPrime++;
if (nthPrime == n) {
return index;
}
}
As the result can only change when nthPrime
does (or n
but n
never changes).
Incidentally, I tried expanding the for
loop as @h.j.k. suggested @h.j.k. suggested but it ran more slowly than the original code. Only a fraction of a millisecond but slower.
for (int i = 2; i * i <= max; i++) {
In my testing it's slightly faster to take the square root of max
rather than multiplying i * i
on each iteration.
for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {
It's only a fraction of a millisecond but a noticeable difference.
for (int j = i; i * j <= max; j++) {
isPrimeArray[i * j] = false;
}
You could simplify this.
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
Then rather than doing two multiplications per iteration, you can do one addition. Of course a good optimizer would notice that both multiplications are the same and only do one.
I prefer names that do not include the type, so I'd just call it isPrime
.
if(isPrime) {
nthPrime++;
}
if(nthPrime == n) {
return index;
}
You compare nthPrime
and n
more often than necessary. You can just say
if (isPrime) {
nthPrime++;
if (nthPrime == n) {
return index;
}
}
As the result can only change when nthPrime
does (or n
but n
never changes).
Incidentally, I tried expanding the for
loop as @h.j.k. suggested but it ran more slowly than the original code. Only a fraction of a millisecond but slower.
for (int i = 2; i * i <= max; i++) {
In my testing it's slightly faster to take the square root of max
rather than multiplying i * i
on each iteration.
for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {
It's only a fraction of a millisecond but a noticeable difference.
for (int j = i; i * j <= max; j++) {
isPrimeArray[i * j] = false;
}
You could simplify this.
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
Then rather than doing two multiplications per iteration, you can do one addition. Of course a good optimizer would notice that both multiplications are the same and only do one.
I prefer names that do not include the type, so I'd just call it isPrime
.
if(isPrime) {
nthPrime++;
}
if(nthPrime == n) {
return index;
}
You compare nthPrime
and n
more often than necessary. You can just say
if (isPrime) {
nthPrime++;
if (nthPrime == n) {
return index;
}
}
As the result can only change when nthPrime
does (or n
but n
never changes).
Incidentally, I tried expanding the for
loop as @h.j.k. suggested but it ran more slowly than the original code. Only a fraction of a millisecond but slower.
for (int i = 2; i * i <= max; i++) {
In my testing it's slightly faster to take the square root of max
rather than multiplying i * i
on each iteration.
for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {
It's only a fraction of a millisecond but a noticeable difference.
for (int j = i; i * j <= max; j++) {
isPrimeArray[i * j] = false;
}
You could simplify this.
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
Then rather than doing two multiplications per iteration, you can do one addition. Of course a good optimizer would notice that both multiplications are the same and only do one.
I prefer names that do not include the type, so I'd just call it isPrime
.
if(isPrime) {
nthPrime++;
}
if(nthPrime == n) {
return index;
}
You compare nthPrime
and n
more often than necessary. You can just say
if (isPrime) {
nthPrime++;
if (nthPrime == n) {
return index;
}
}
As the result can only change when nthPrime
does (or n
but n
never changes).
Incidentally, I tried expanding the for
loop as @h.j.k. suggested but it ran more slowly than the original code. Only a fraction of a millisecond but slower.