Home
Outline/Policy Summary Approach References Homework View Upload Problems: Archive Archive Mirror Categories Guidelines Coding Tips Contests: Regional NA Qualifier Extra: Grades Class: CSC 2700 Section 02 Tureaud Hall 101 Tuesday 6:30 PM  8:20 PM Previous: 2012 Spring 2011 Fall 
Number TheoryTo borrow from Programming Challenges, number theory in programming contests includes the following:
References PrimesIn general, I believe 99% of dealing with primes in a problem boils down to loading a list with the first N prime numbers via the Sieve of Erasthones:
primeCnt = 0; for (i=0; i< UPPERLIMIT; i++) a[i] = i; for (i=2; i<UPPERLIMIT; i++) { /* for */ if (0 != a[i]) { /* found a prime */ p[primeCnt] = i; primeCnt++; for (j=i*2; j < UPPERLIMIT; j=j+i) a[j] = 0; } /* found a prime */ } /* for */ Of course, what do you do with the list? Using it to determine prime factors might be common.
DivisibilityIn one sense divisibility is easy  use mod. Here are some neat rules for divisibility:
Modular ArithmeticModular arithmetic is sometimes called clock arithmetic. It is the idea that the set of numbers is finite and that you wrap to the begining when you go past the end (like a clock does). Lots of problems rely on these ideas (such as the "every nth person out" problems). A typical code snippet might be something like: n = (n + 1) mod MAX
When you think about it, this is how all arithmetic works. 9 + 1 = 10 When you add one to the largest
base 10 digit (9) you get zero for an answer with a carry into the next column. You do the same in modular
arithmetic except for forget the carry.

The statements and opinions included in these pages are those of only. Any statements and
opinions included in these pages are not those of Louisiana
State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Isaac Traxler