Corning Community College
CSCS2330 Discrete Structures
Using the TIC-80 fantasy console simulator on your pi, implement a program that visually displays a range of values (lower and upper bounds adjustable by the user) that colorfully displays whether each value is a prime or composite value.
The algorithm you are to implement is the sieve of eratosthenes, which takes a completely different approach to prime/composite determination than the trial-by-division approach we've explored in pnf0/pnf1.
Time how long it takes to execute (displaying elapsed time for the run at its conclusion; this is useful for comparisons), and display this result, especially in relation to the work load and algorithm used.
Additionally, the entire class will be participating in documenting and filling out this project page. It is the responsibility of EACH class member to:
The Sieve of Eratosthenes was discovered by Eratosthenes who was born in 276 B.C. This Makes this method over 2200 years old. The algorithm is not too complex, and relatively easy to understand. It works by determined a list of prime numbers from 2, to a given number. It works by checking weather or not numbers within the given range have been marked as composite yet. For example, if you wanted to determine what numbers are prime up to 100, you would start at 2. Because 2 is at the beginning of the range, it has not been marked as composite and therefore is prime. But now we must say that all multiples of 2, up to 100, are composite(4,6,8,etc.). Now we would move on to the next number in the range, which is obviously 3. 3 has not been marked which means it is prime. Now again, we must say that all multiples of 3 are composite(6,9,12,etc.). We now move on to 4, but 4 has already been marked as composite, so we don't need to do anything. We can just move on to 5, which is unmarked. We now mark it as being prime, and again all multiples of 5 are composite(10,15,20,etc.). This process repeats until we have reached the end of the given range(100).
Before we can jump into how to program our prime number detection algorithm, we must understand the basic rules of prime numbers.
Prime Numbers Must Be:
With your knowledge of programming and the rules of prime numbers, you should be able to make a detection algorithm now! There are different computational methods for figuring out the primality of a number, we will take a look at one algorithm which is a bit more difficult to understand.
Originating in ancient Greece (probably), the Sieve of Eratosthenes is an mathematical algorithm for finding all prime numbers up to a given limit. The way the Sieve accomplishes this is by marking the multiples of each prime as composite (starting with 2, the first prime). Anything marked is known composite, and anything unmarked is tested. The algorithm then continues up until the root* of the limit (say for a limit, N, of 100, the algorithm would continue up to 10). This is a little confusing at first, but here's a video explaining it well: https://www.youtube.com/watch?v=P__PsS2J_y8&t=3s
Note: in order to use the Sieve properly, you have to start at 2. Because of this, when calculating ranges which begin above 2 (for example, 5000-5010), the SoE may appear to actually be slower, as where the previous algorithms need only perform the calculations on 5000-5010, the SoE must calculate all of the primes from 2-5010. Barring implementation-specific edge cases, however, this new algorithm should always outperform the old ones even with full optimization enabled.
* By only proceeding up to the root of the upper bound, the primes up to that upper bound will be found just fine, but it may be worth mentioning that there will be no way to “pick back up” from the upper bound if more calculation is desired - the sieve MUST effectively progress from 2 up to sqrt(UPPER), and in cases where more calculation is desired on top of what has been previously done, you would have to either store all found primes and initialize the array with their multiples marked, or save the array previously worked upon and pick up from the sqrt(UPPER) index.
Since the Sieve of Eratosthenes relies on what is effectively an array of Booleans, the process of implementation must begin roughly there. An array must be initialized of size N-2, where N is the upper bound of the user-selected range. This array will effectively be one of potentially prime numbers ranging from 2 to N. As calculations begin, this array must be walked effectively in increments of the currently selected prime (so, when starting at prime 2, walk in increments of 2) and set each selected index to FALSE or whatever not-prime should be represented as. That walking process must occur every time an un-marked-as-not-prime is encountered, as every time that happens, the selected number is prime and its multiples must be noted. This idea may be vaguely imagined as a for loop where the do-every-time action is not something like `i++`, but instead `i += currentNumber`.
Given the speed of the SoE, the fun animated experience of many implementations may no longer be viable without severely handicapping old implementations and reworking animation code. As this algorithm may often finish by the time frame 1 is rendered (or whichever frame the calculation starts on), there is significantly less potential for animation (in fact, about 0) during the process of calculation. This does, however, still leave the possibility of post-finish animations on the table (rainbow numbers, flying unicorns, flashing, etc.) which may be well-worth exploring.
In order to submit the game file, our “tic” file, the file must be added to your lab46 somehow. This can be achieved through FTP software, such as FileZilla, or more easily by putting the file onto your Pi then pushing to your repo and pulling from lab46.
Of course, if you are using the TIC-80 application on your Pi then the file will exist there when saved.
To submit this project using the submit tool, run the following command at your lab46 prompt:
lab46:~/src/SEMESTER/DESIG/pnfX$ submit DESIG pnfX GAMENAME.tic Submitting DESIG project "pnfX": -> GAMENAME.tic(OK) SUCCESSFULLY SUBMITTED
NOTE: “GAMENAME” here is the name of your game. Please do not literally submit a tic file named “GAMENAME”, come up with a creative name for your game.
I'll be looking for the following:
78:pnf2:final tally of results (78/78) *:pnf2:no errors, program runs without issue in TIC-80 [13/13] *:pnf2:user can specify lower and upper bounds at runtime [13/13] *:pnf2:specified algorithms are implemented and functional [26/26] *:pnf2:timing of process is implemented, functional, shown [13/13] *:pnf2:project page contributions as per project specifications [13/13]
Additionally: