[Brewer]

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

def main():                                                                                                                                                      
    print getPrimes()
 
def getPrimes():
    # This script won't generate the first
    # prime number (2), so we start with
    # 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

[baavgai]

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
				cache.add(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.

[Nallo]

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

[koppinjo]

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

[jaycode]

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!

[Tipro]

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."

[desirocks]

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..!

[extremeblueness]

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

public class PrimeNumberFinder {
public class PrimeNumberFinder {
    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 class PrimeNumberFinder {
    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);    
    }
}