DEV Community


Generating Prime Numbers: Reloaded

seanolad profile image Sean ・1 min read

So This Again

After posting my previous post I got okay feedback, but there was a key problem. My method to getting prime numbers was wrong. So I decided to create an alternative method that I know is fool proof.

My working solution

So this solution is pretty simple so I'm sure that even beginners will understand(last time I wrote my code in c++, ruby, python, and js, this time only python).

The Code:

Takes user input and generates all the primes under it(including the number itself if it's prime)

How would you have done it?

Discussion (2)

nam288 profile image
Nam H. Le

Some advice:

  1. Your is_prime function has O(n) complexity. You can test only divisors in range [2, sqrt(n)] because if n has any divisor in range [sqrt(n), n) so it also has another in range [2, sqrt(n)].
  2. You can use Sieve of Eratosthenes to solve your original problem. :)
thorstenhirsch profile image
Thorsten Hirsch

Glad you've found the right approach. :-)

Forem Open with the Forem app