Prime Optimization

Question

I decided to make a script to list all the prime numbers up to the input number. First draft was slow. Some optimization sped it up a bit. What else can I do to improve the speed that this works?

https://code.sololearn.com/cx53E4jy8alU/?ref=app

Answer 1

The most optimal way of finding primes is to first find all primes up to the square root of that number, then see if those primes are divisible. (This requires an extra method/function)

The more common way is to check all odd numbers up to the square root of the number your checking. (with an exception of 2)
Check my computation speed comparer code for an example of that. In that code I compare 2 ways of finding primes by their computatuon speeds.
The code: https://code.sololearn.com/cpfUWe23IG3o/?ref=app

Most sololearners I see just check divisibility of every number up to the number that you want to check is a prime. Don't do this, it's not effecient.

Answer 2

If you want to find all primes up to a number, then you will have to do it a bit differently. That was mainly for just determining if something was a prime. 😗

For finding all primes. hm.. Perhaps you could check to see all primes up to the square root of that number, and only compare divisibility with those. So you'd keep searching all odd numbers up to say 169, but only compare with numbers 2,3,5,7,11,13.

I think that'll do 😅

Answer 3

I don't understand. say I want to know all the primes up to 169. the sqrt of 169 is 13.. how does this get me to the 39 primes I am looking for?

Answer 4

ah, gotcha lol. Guess I will keep playing and see where I can save some computing. Thanks for the tips tho, I will find a way to work them into something