# 1000th prime number generator problem!

• (2 Pages)
• 1
• 2

## 22 Replies - 32230 Views - Last Post: 22 October 2012 - 08:27 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=176421&amp;s=07df58e7afca238902ab07edecda40bc&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 Brewer

• Awesome

Reputation: 179
• Posts: 1,044
• Joined: 14-June 10

## Re: 1000th prime number generator problem!

Posted 18 July 2011 - 05:14 AM

Well everyone else is posting there solutions, so here's mine:

def main():
print getPrimes()

def getPrimes():
# This script won't generate the first
# primes = 1, where primes is the # of
# primes we have generated.
primes = 1
num = 1
while primes < 1000:
num += 2
if isPrime(num):
primes += 1
# Returns [1000, num] where num is the
# 1000th prime number.
return primes, num

def isPrime(n):
# Assert that n is not even. Even numbers
# cannot be prime, so why bother with them?
assert n % 2 != 0

# All values of n will be odd, so we don't need to
# check and see if they are divisible by 1 or 2.
# This also means that we don't need to check and
# see if n is divisible by any even numbers, so we
# step by 2 each iteration.
for i in range(3, n/2, 2):
if n % i == 0: return False
return True

if __name__ == "__main__":
main()

This post has been edited by Brewer: 18 July 2011 - 05:15 AM

### #17 baavgai

• Dreaming Coder

Reputation: 6053
• Posts: 13,107
• Joined: 16-October 07

## Re: 1000th prime number generator problem!

Posted 18 July 2011 - 07:06 AM

Since code is out, I supose I'd do it like so:

def primeGenerator():
def isPrime(cache, n):
for value in cache:
if n % value == 0:
return False
return True

(cache, last) = (set(),2)
while True:
if last not in cache:
if isPrime(cache, last):
yield last
last += 1

def nthPrime(n):
if n==1:
return 1
else:
g = primeGenerator()
for i in range(n-2):
g.next()
return g.next()

Yes, there's extra code. However, it's reasonably fast for the constraint of not knowing how many values are in the set. Plus, generators are cool.

### #18 Nallo

• D.I.C Regular

Reputation: 163
• Posts: 256
• Joined: 19-July 09

## Re: 1000th prime number generator problem!

Posted 19 July 2011 - 10:05 AM

Well, now that everyone has thrown out code examples in an old thread. I want to do so too:

My favorite prime generators:

The first one is a bit nonstandard as it uses a heap.
#using heap based implementation of sieve of erastothenes
#well not exactly erastotheness, as we might cross of
#a few numbers more than once
import heapq

def prime_generator():
yield 2
crossed_prime = [(2*2, 2)]
candidate = 3
while True:
minimal_crossed_of, prime = crossed_prime[0] #peek at heap
if candidate < minimal_crossed_of: #candidate is prime
yield candidate
heapq.heappush(crossed_prime, (candidate ** 2, candidate))
candidate += 2
elif candidate == minimal_crossed_of: #candidate was crossed of
candidate += 2
else: #need to cross of more
heapq.heappushpop(crossed_prime,
(minimal_crossed_of + prime, prime))

def nth_prime(n):
pg = prime_generator()
for i in xrange(n-1):
pg.next()
return pg.next()

print nth_prime(1000)

The second one is a bit hard to read, but the fastest I could come up with for big primes.
Not just measly little ones like 1000th prime. It can easily do 1000000th prime :-)
import itertools

class Primes(object):
"""class for generating primes
works by extending known_primes by applying
a sieve to intervalls of numbers when needed.

example usage:
pr = Primes()
for p in pr:
if p > 1000:
break
print p,

print "millionth prime: ", pr.nth(1000000)

"""
def __init__(self, intervall_len = 30000):
#intervall_len below 25000 or above 50000 seem decisively slower

#process first interval of numbers
intervall = [None, None] + range(2, intervall_len)
for p in xrange(2, int(intervall_len ** 0.5) + 1):
if intervall[p] is not None:
intervall[p * p::P/>] = [None] * ((intervall_len - 1 - p * p)
// p + 1)
self.known_primes = filter(None, intervall)
self.hi_bound = intervall_len
self._intervall_len = intervall_len

def extend_known_primes(self):
"""extends self.known_primes to include the primes from the
next intervall
"""
intervall = range(self.hi_bound, self.hi_bound + self._intervall_len)
for p in self.known_primes:
if p * p > (self.hi_bound + self._intervall_len):
break
start = (p - self.hi_bound) % p
intervall[start::P/>] = [None] * ((self._intervall_len - 1 - start)
// p + 1)
self.known_primes += filter(None, intervall)
self.hi_bound += self._intervall_len

def __iter__(self):
"""infinite generator for all primes (until memory runs out)"""
return (self.nth(i) for i in itertools.count(1))

def nth(self, n):
"""returns nth prime"""
try:
return self.known_primes[n - 1]
except IndexError:
while len(self.known_primes) < n:
self.extend_known_primes()
return self.known_primes[n - 1]

pg = Primes()
print pg.nth(1000)

By the way baavgai, you made an error by one ... 1 is not a prime ;-) Though I like it for its readability.

This post has been edited by Nallo: 19 July 2011 - 10:09 AM

### #19 koppinjo

Reputation: 0
• Posts: 1
• Joined: 25-April 12

## Re: 1000th prime number generator problem!

Posted 25 April 2012 - 01:22 PM

I'm doing this for MIT OCW and have zero programming experience (apart from on-the-job learning SQL and reading through legacy VB for about a year). This code gets the correct answer using only what has been taught through the first two, maybe three lectures and using it to calculate the 10000th prime number takes...awhile...
nthPrime = input('which prime number would you like to find? (please enter an integer): ')
print('Please wait a moment while the number is calculated...')
p = 1
n = 2
d = 2
primeCounter = p
while (primeCounter<=int(nthPrime)):
while d<=int(n/2):
if n%d != 0:
d=d+1
elif n%d == 0:
d=2
n=n+1
primeCounter = primeCounter + 1
n=n+1
d=2
print('Prime number ' + str(nthPrime) + ' is ' + str(n-1))

I wanted to make it a bit more robust than only calculating one specific number (the 1000th) and would like to put in some type checking but it isn't working correctly (because I am missing something of course). I tried putting in an if nthPrime == str(nthPrime): {print a message asking for an integer and take in another input}, but when I did this even if I put in an integer it still saw the assertion to be true and asked for an integer...

Any advice on type checking? Thanks! This is my first post

### #20 jaycode

Reputation: 0
• Posts: 1
• Joined: 14-June 12

## Re: 1000th prime number generator problem!

Posted 14 June 2012 - 02:14 PM

handihans, on 24 May 2011 - 02:36 PM, said:

try this:

for n in range(4, 20):
for x in range(2, n):
if n % x == 0:
break
else:
# loop fell through without finding a factor
print n, 'is a prime number'

you can change the range if you want more or less primes
hope it helps!

Thanks for the help - I'm working on the same problem (still a beginner). The only problem with the code you provided is that it won't generate the first 1000 numbers.. if we wanted to do every number in between 1 and 1000, that would be perfect, but to generate the first thousand I added something in to your code that will allow us to do that:

p = 999
n = 2
print '2 is a prime number'
while(p>0):
n = n + 1
for x in range(2, n):
if n % x == 0:
break
else:
# loop fell through without finding a factor
print n, 'is a prime number'
p = p - 1

Since we know 2 is a prime number, we can start there and test every number. If you assign p as 999 to start, the loop will countdown from 999 to 1 and give us the next 999 prime numbers.

I am working on the MIT OCW as well, and we did not learn "break" yet as far as I can remember, so technically I think I still need to look at another way, but nice to know this is one way!

### #21 Tipro

Reputation: 0
• Posts: 1
• Joined: 30-July 12

## Re: 1000th prime number generator problem!

Posted 30 July 2012 - 09:27 AM

I'm just learning to program (for fun, not school) and saw this as a beginner challenge somewhere else. Just wanted to post my take on this program.

n = input('Enter the prime you wish to find: ')
a, y = 1, 0
while y < n:
a = a + 1
for b in range(2, a):
if a % b == 0:
break
else:   ## make sure this line is detended from the previous 'if' stmt
y = y + 1
print a, "is the", y, "prime number."

### #22 desirocks

Reputation: 0
• Posts: 9
• Joined: 12-June 09

## Re: 1000th prime number generator problem!

Posted 10 September 2012 - 06:05 PM

def get_nth_prime_number(n):
"""Calculates the nth prime number from start"""

count = 1
for i in range(2,1000000):
isprime = 1
for j in range(2,i):
if(i==j):
continue
elif(i%j==0):
isprime=0
if(isprime):
count=count + 1
if count == n:
print("The %dth prime number is %d" % (count, i))
break

def get_data():
"""Gets the input from the user"""

n = input("Get the nth prime number where n = ")
return n

if __name__ =='__main__':
get_nth_prime_number(get_data())

This is the simplest solution that I could find. It is not that fast but given the constraints, this works..!

### #23 extremeblueness

Reputation: 16
• Posts: 186
• Joined: 22-October 12

## Re: 1000th prime number generator problem!

Posted 22 October 2012 - 08:27 PM

Okay. I'm a beginner programmer, and I created a PNG (prime number generator) earlier today. Here's my code:

public static void main (String args[]){
int primes = 2, number = 1;

primefinder:
for ( ; number <= 1000 ; primes++ ) {
primes++;
for ( int primecheck = primes; ; ) {
primecheck--;
for ( ; primecheck > 1 ; primecheck-- ) {

if ( primes % primecheck == 0){
continue primefinder;
}
}
number++;
continue primefinder;
}
}
primes--;
number--;
System.out.println("Prime #" + number + ": " + primes);
}
}

This was originally created to be an infinite PNG (at least to the limit of a long variable), but then when my computer nearly crashed, I made it limited.

Just realized that this generates the 1001st prime. Here's the corrected code:

public static void main (String args[]){
int primes = 2, number = 1;

primefinder:
for ( ; number <= 999 ; primes++ ) {
primes++;
for ( int primecheck = primes; ; ) {
primecheck--;
for ( ; primecheck > 1 ; primecheck-- ) {

if ( primes % primecheck == 0){
continue primefinder;
}
}
number++;
continue primefinder;
}
}
primes--;
System.out.println("Prime #" + number + ": " + primes);
}
}