# MI : Ps1a

## Ps1a - 2nd assignment

Write a program that finds the 1000th prime number. This is to be done in python, but I will attempt to port my code to other languages, again. At the time of this writing, I have successfully ported it to tcl and bash (sort of…the bash takes a different approach, but gives the same result, so not precisely a port).

This time, again, I haven't “attended” the appropriate lecture (although I did finally watch the 1st class, sort of. I have difficulty focusing on online videos, really. It's about the worst way for me to try and learn. I wish they would just write the lecture notes down and point to a tutorial, or something. I learn well by reading and doing, but not by watching a video).

## Python

#!/usr/bin/env python # Problem Set 1 # Name: Tony Baldwin # Collaborators: 0 # Time: 2.5 hrs import math # start with a beginning list of primes. primes = [2,3,5] print("listing prime numbers: \n1\n2\n3\n5") # we know this next one works, but we need to query more numbers, and this is as good a place to start as any q = 7 # Now, note that our initial list does not contain 1. # This is because, in our test below, we are testing to see if we can evenly divide our query, q, # evenly by any prime number less than q, and, of course, all numbers are evenly divisble by 1, # so that would wreck our test. # Thus, we will conduct our test until the length of our list is 999, at which point, # we will have found the 1000th prime. while len(primes) <= 999: # here, we divide our query no. q by all of the primes less than q. # if we get a remainder of 0, we stop that loop, add 2 to q # since we know that no even number is prime, and try the test with a new number for i in primes: if q % i == 0: q += 2 break else: # if we don't get a remainder of 0, the number is prime. # we print it out and add it to the list, then add 2 to q and go back to our test. print(q) primes.append(q) q += 2 # since this last run will have added 2 to our final successful query, # I subtract it again. winner = q - 2 print("And, our winner of the 1000th prime number contest is %s!" % winner) exit

(pastebinned here with results, too)

I honestly wanted to try and find a better, more efficient way to do this, especially since this solution is pretty well what I saw others doing, but I haven't the mathematical prowess. I was looking at tests for primality here, but I don't get it. Some of the stuff on that page may as well be Chinese, to me. Recall, I am a translator, but Chinese isn't among my languages. But it seems were I able to comprehend the math going on there, I might be able to generate a more efficient test. I don't know.

A classmate solved this with three fewer lines of code. When you have only 15, or 12 lines, 3 lines is a significant percentage of code. I'm jealous.

Especially, the fact that this took me 2.5 hours, even though I peeked at a classmate's code, is irking.

But, this works, and gives output that looks like this.

I think the comments in the code explain how it works well enough.

tonybaldwin September 03, 2011, at 04:24 PM

## TCL

Okay, admittedly with some gracious assistance from #tcl @freenode, we now have this working in tcl.

Here, I had to set up a boolean test value, because a foreach loop in tcl is tricky. Now, I'd seen some classmates using such a boolean value in their python, but I managed to avoid that. Whether their code or mine is more efficient as a result remains for better hackers than I to decide, but here, in tcl, it seemed necessary.

#!/usr/bin/env tclsh # print first 1000 primes. # by tony baldwin global qprime set primes [ list 2 3 5 ] puts "Listing prime numbers: \n1\n2\n3\n5" set q 7 while {[llength $primes] < 1000} { set qprime 1 foreach i $primes { if { $q % $i == 0 } { set qprime 0 break } } if { $qprime } { puts $q lappend primes $q } incr q 2 } set winner [expr { $q - 2 }] puts "The 1000th prime number is $q."

tonybaldwin September 03, 2011, at 11:39 PM

## Bash

Doing this in bash was a bit different, since appending lists and getting their length and stuff is, at least for me, troublesome. Thankfully, bash has a nifty command called factor.

#!/bin/bash # find the 1000th prime number. # tony baldwin # Load output of `factor` into array. # this gives something like factor 12 # 12: 2 2 3 (factors it to primes) # so, if it IS a prime, you get, for instance # 7: 7 (only two elements in your array!) # so we test for a third element of the array # if there is no third element, the number is prime len=0 for n in $(seq 100000); do factors=( $(factor $n) ) if [ -z "${factors[2]}" ] then len=$[len+1] echo -e "$n" if [ $len -eq 1001 ]; then echo -e "The 1000th prime number is $n.\n" exit fi fi done exit

tonybaldwin September 03, 2011, at 08:17 PM

## Time

So, I got curious which of these was most “efficient”. Visually, I could already determine that bash was the slowest, by a long shot, but I decided to time them, and here are my results:

Python | Tcl | Bash | |||

real 0m0.114s user 0m0.112s sys 0m0.000s | real 0m0.460s user 0m0.452s sys 0m0.008s | real 0m14.966s user 0m11.049s sys 0m7.908s |

Looks like python is winning the race here. I wonder if the added boolean switch in the tcl is causing significant wind resistance.

If/when I get some other languages up, I'll expand on the time tests.

~~DISQUS~~