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?
Jump to PostCheck 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.
Jump to PostYou should have listened and read Python snippet at ...
http://www.daniweb.com/software-development/python/threads/465305/python-prime-number-code-not-working#post2026050Actually, a good sieve algorithm will run N=1000000 in about 0.1 to 0.2 seconds.
If you use Python module numpy, you can do this in 0.012 seconds.
You should have listened and read Python snippet at ...
http://www.daniweb.com/software-development/python/threads/465305/python-prime-number-code-not-working#post2026050
Actually, a good sieve algorithm will run N=1000000 in about 0.1 to 0.2 seconds.
If you use Python module numpy, you can do this in 0.012 seconds.
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.
Only your devisor range can be limited with the sqrt() value!
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.