I have created a program to find all the prime numbers less than N.

When N is around 10^4, the program runs fast and efficiently.
If I increse it to 10^5 no output is given, even if i let it run for an hour or so.

Is there anyway I could get my program to output for higher values of N?

Check out this.

There are highly optimized codes there for generating prime numbers. Including my one :)
They give you primes to 10**6 in seconds.

If you post your code we can pinpoint, why is it so slow.

10 to the 5=100,000 and you only have to test up to the square root and every other number, i.e. not even, which is slightly more than 150 numbers if my arithmetic is correct. So it has to be some other problem. Check any while() loops and that you are not sending the same number(s) through the test over and over.

Edited 3 Years Ago by woooee

Your original algorithm will be much too slow, for N = 1000000 you have a million calls to your function is_divisible(), and within that function you have a loop with at least sqrt(N) calculations. Even if you loop only through odd numbers that is close to a half billion calculations.

I hope you can pick something better from the python forum here. There is always module timeit to time your progress.

Python has module cProfile that can be applied to show you how many times a particular call is made and how much time it consumes.

Edited 3 Years Ago by vegaseat

This question has already been answered. Start a new discussion instead.