6. Mathematical Algorithms Cont.
i. A prime factorization is an expression of an integer as a product of primes
ii. Fundamental Theorem of Arithmetic: Every integer greater than 1 has a
unique prime factorization – it can always be written in one and only one
way as a product of prime numbers.
g. Greatest Common Divisor
i. The GCD of two integers “m” and “n” denoted gcd(m,n) is the largest
integer able to be divided into both.
ii. Euclidian Algorithm
a. Efficiently computes VERY large numbers
2. Suppose m>n. If n divides m, then clearly gcd(m,n) = n.
Otherwise, let d be any divisor of both m and n.
a. Then, d also divides the difference of m and n, and all
multiples of m and n.
3. Thus, if d divides both m and n, then it also divides m-n, m-2n, m-
3n, … up to m%n. Hence:
a. gcd(m,n) = gcd(m, m%n) on the condition that m>n and n
divides into m.
7. Structure of C
f. A program is a sequence of valid characters
g. The compiler first executes all compiler directives (lines beginning with #) then
splits the sequence of characters into whitespace and tokens.
i. Six type of tokens:
a. Words with a prescribed meaning. Cannot be redefined
a. Names of variables or functions, etc…
b. They cannot begin with a digit, and can be any length, but
the program will read only the first 31 characters.
3. Operators and Punctuations a. Perform operations, and separate words
4. Programming Errors (Bugs)
a. With syntax (compiler) errors, the program won’t compile.
They usually consist of typos, mis-punctuations, and
b. With run-time errors, the program compiles successfully
but crashes when executed (e.g. division by 0, or infinite
c. With logic errors, the program runs, but produces the
wrong desired output
h. Four Steps of Software Writing
i. Analyze: Define input and desired output
ii. Design: Decide on data structures and algorithm
iii. Implement: Code using chosen language
iv. Debug and debug again and again and so forth and again and etc and
8. More Macros (#define)
f. Tells compiler to represent a term with a constant.
i. Done during pre-compiling, before anything else.
ii. A macro is a constant, not a variable, and cannot change during the
runtime of the program.
g. When to use Macros vs Constant
i. Macros simplify changes across the program where the macro exists, you
only need to change the macro value once.
ii. Clarifies program: the term “CLASSSIZE” is clearer than the constant
iii. Eliminates retyping long constants
h. When to use Macro vs Variables
i. Faster access (no need to check variable change)
ii. Classifies this as a constant that does not change.
i. Macros can be used to represent:
ii. strings iii. operators
j. Recursive Macros
i. Macros can use other macros:
1. #define TWO_PI 2*3.14159 is the same as
a. #define PI 3.14159
#define TWO_PI 2*PI
k. Macros can be defined in terms of arguments or variables.
iii. When including variables in a