0

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

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

8th Aug 2023, 10:52 AM
Swen
4 Answers
+ 5
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".
8th Aug 2023, 11:09 AM
Mozzy
Mozzy - avatar
+ 2
Wow, thanks a lot for great advice, Mozzy. Very helpful hints to improve one of my first programs.
8th Aug 2023, 11:27 AM
Swen
+ 2
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
25th Aug 2023, 5:56 PM
Han Tong
Han Tong - avatar
0
Thank you Han Tong for your detailed explanation. This is very helpful and very much appreciated.
2nd Oct 2023, 2:40 AM
Swen