How to calculate prime numbers in Python? Please have a look and comment on any improvements you see. Thanks!

Question

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

Answer 1

Hi Swen Göbbels

In the `createPrimeList()` function:
- `prime_list` shoud be an empty list, 0 isn't a prime number
- `i` should start from 2 instead of 0, since 2 is the first prime number
- a `for` loop would be more appropriate here instead of `while` loop, since we have a `range` value
- should choose another name for the `range` variable since it is already a name for a built-in function in Python

There are several ways to optimize the `isPrime()` function so that it can better handle the testing larger numbers. I'll leave this to you to research and implement. Simply Google "primality test".

Answer 2

Wow, thanks a lot for great advice, Mozzy. Very helpful hints to improve one of my first programs.

Answer 3

Your code:

def isPrime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True

- This is correct but you can make it better. The only even prime number is 2 otherwise are not. So to eliminate steps, add
if n == 2 or n == 3: return True
if n % 2 == 0: return False

- time to run now decreases a half.
for i in range (3, n + 1, 2):
…
- now we will start from 3,
- n + 1 because if not, it just runs to n - 1
- jump 2 because after an odd number is an even which we eliminate by def if n % 2 == 0 it is not a prime.

- deep and deeper, check this: for example n = 36
we have n = 36
= 2 * 18
= 3 * 12
= 4 * 9
= 6 * 6 <- look at this
= 9 * 4
= 12 * 3
= 18 * 2

when you already check those numbers above 6 * 6, do you need to check them again below? the answer is no, it just wastes your time. So now don’t go from 3, to n + 1, jump 2. Just go from 3, to sqrt(n), and jump 2.

try and see how super faster you get if n is about millions or billions

Answer 4

Thank you Han Tong for your detailed explanation. This is very helpful and very much appreciated.