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.

tonybaldwin


~~DISQUS~~