I need to find the nth prime number, in the fastest way possible in Ruby or Python:
require "prime"
puts Prime.first(n).join("")
This takes a lot of time for numbers >= 100000.
How do I optimize this code?
Asked
Active
Viewed 1,211 times
0
the Tin Man
- 158,662
- 42
- 215
- 303
-
1the fastest way would be to just have a list of all the primes and then just index it... however its not realistic since if you put 100000 primes in the list I would ask for the 100001th one. but you can do sieve of erathmus(sp?) and seed it with the first 1000 or so primes (or 100000 or whatever) (or even just the first but the more primes you seed it with the faster it should be) – Joran Beasley Sep 13 '13 at 18:43
-
2Python: [Fastest way to list all primes below N in python](http://stackoverflow.com/q/2068372) – Martijn Pieters Sep 13 '13 at 18:48
-
2@MartijnPieters Finding the nth prime is very different from finding all primes below n :) – Shashank Sep 13 '13 at 20:49
-
@Shashank: perhaps, and I did not vote to close this as a dupe. Yet the other post must hold *some* value in relation to this question. – Martijn Pieters Sep 13 '13 at 21:10
-
Monkeypatching the `Integer` and `Prime` classes with the code found [here](http://forums.xkcd.com/viewtopic.php?f=11&t=31481) leads to marginal improvements (for n = 200000, from 11.52s to 9.08s on my machine). – Jacob Brown Sep 13 '13 at 21:42
-
@Joran Beasley That is the Sieve of Eratosthenes. You can fit 100,000 primes into 50,000 bits (even numbers can be ignored). – rossum Sep 16 '13 at 17:45
-
see the optimized algorithm here: http://stackoverflow.com/a/32806718/290338 – Anatoly Sep 28 '15 at 12:01
3 Answers
0
Give this a try:-
# Steps
# List first 'n' prime
# Choose the very last one
require "prime"
def nprime(n)
(Prime.first n).last
end
puts nprime(10001)
It gave me the answer preety quick:
$ ruby nprime.rb
104743
dahal
- 94
- 9
0
You may try this dynamic program in python, this looks up in a dictionary of primes(built dynamically by the program itself), which is initially empty and it gets faster as you find larger primes.
dict = {}
def prime(x):
dict[1] = 2
s = x
if x in dict:
return dict[s]
else:
while s > 0:
if s in dict:
pno = int(dict[s]) + 1
break
s-=1
while s < x:
m = 1
while m <= s:
if pno % dict[m] == 0:
pno+=1
m=1
else:
m+=1
dict[s+1]= pno
s+=1
return dict[x]
initially build the dictionary for lower primes for speeding up higher ones. Example to find the 10000th prime, do the following in python shell ahen running the module: prime(1000) prime(5000) prime(10000)
user3903149
- 1
- 1
