1000th prime number generator problem!

it'se a beginner's prog, no fancy keywords or functions used

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 29603 Views - Last Post: 22 October 2012 - 08:27 PM Rate Topic: -----

#16 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • 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
    # 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

Was This Post Helpful? 0
  • +
  • -

#17 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5826
  • View blog
  • Posts: 12,678
  • 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
				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.
Was This Post Helpful? 1
  • +
  • -

#18 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • 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

Was This Post Helpful? 0
  • +
  • -

#19 koppinjo  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

#20 jaycode  Icon User is offline

  • New D.I.C Head

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

Re: 1000th prime number generator problem!

Posted 14 June 2012 - 02:14 PM

View Posthandihans, 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!
Was This Post Helpful? 0
  • +
  • -

#21 Tipro  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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."


Was This Post Helpful? 0
  • +
  • -

#22 desirocks  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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..!
Was This Post Helpful? 0
  • +
  • -

#23 extremeblueness  Icon User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • 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 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);    
    }
}


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2