Algorithm writing tips?

Something I thought about later... sqrt is not cheap (iirc it uses Newton's method to approximate?).

primesList.get(i) <= Math.sqrt(n)
Use
primeslist.get(i)**2 <= n

Depends on what language you use. Shouldn't it equal to Math.pow(n, 0.5), which uses logaritms?

edit: Implementation-dependent:


Anyway, I save the value instead of recalculating it. e.g:

sqrt = (int) Math.sqrt(n)
for (i = 5; i < sqrt; i += 6)

instead of:

for (i = 5; i < Math.sqrt(n); i += 6)

Logarithms in turn would use iteration most likely though, they're another non basic operation.

Prestoring the value would work except I think its being called a lot of times and would still have to calculate the more complicated sqrt instead of just ^2 every time.

Logarithms in turn would use iteration most likely though, they're another non basic operation.

Prestoring the value would work except I think its being called a lot of times and would still have to calculate the more complicated sqrt instead of just ^2 every time.

For the purposes of the isPrime() function, calculating a pre-stored square of the number being indexed doesn't work. Pre-stored variables are a good choice only on the static limits of a loop, and assuming said loops aren't extremely short in duration.

For the function isPrime(int n):

Code:

if(preliminary tests failed) return false;
int upperLimit = sqrt(n);
for(int factor = x; factor <= upperLimit; increment factor by f(y)){
  if(n % factor == 0) return false;
}
return true;

Code:

if(preliminary tests failed) return false;
for(int factor = x; factor*factor <= n; increment factor by f(y)){
  if(n % factor == 0) return false;
}
return true;

Pre-storing the sqrt of n is noticeably faster than calculating the square of a number when used in the final algorithm I posted.


EDIT: What's the difference in Run Time and Real Time? (referring to DS's picture)

EDIT2: Thoughts confirmed xD

EDIT: What's the difference in Run Time and Real Time? (referring to DS's picture)

Real time = lag, if any.

 Spoiler

No lag on faster computers!