Friday, July 8, 2011

MIT 6.00 Problem Set 1 - Problem 1 Answer


Python Code Answer:

#Problem Set 1 - Problem 1

#prime_count = 1 since first prime number 2 is known
#candidate = 1 inc by 2 gives odd numbers
#stop checking once nonprime found with break
#trial division method, divisors on interval (1, sqrt(candidate)]

candidate = 1
prime_count = 1
column = 1
nth_prime = 1000
max_column = 10
column_pad = 6

print str(2).center(column_pad),

while prime_count < nth_prime:
    divisor = 2
    prime = 1
    candidate += 2

    while divisor <= candidate**0.5:
        if candidate % divisor == 0:
            prime = 0
            break

        divisor += 1
                
    if prime:
        prime_count += 1

        print str(candidate).center(column_pad),
        column += 1

        if column == max_column:
            print
            column = 0

        if prime_count == nth_prime:
            print ("The 1000th prime is: ", candidate)

Output:



 2      3      5      7      11     13     17     19     23     29
 31     37     41     43     47     53     59     61     67     71
 73     79     83     89     97    101    103    107    109    113
.
.
.


 7649   7669   7673   7681   7687   7691   7699   7703   7717   7723
 7727   7741   7753   7757   7759   7789   7793   7817   7823   7829
 7841   7853   7867   7873   7877   7879   7883   7901   7907   7919
('The 1000th prime is: ', 7919)


http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

2 comments: