Transcript Class 12

CSCI 125 & 161
Lecture 12
Martin van Bommel
Prime Numbers
• Prime number is one whose only divisors
are the number 1 and itself
• Therefore, number is prime if it has two
positive divisors
• One way to test for prime is to count its
divisors
Prime- First Try
bool IsPrime(int n)
{
int i, divisors = 0;
for (i=1; i<=n; i++)
{
if (n % i == 0) divisors++;
}
return (divisors == 2);
}
Prime - Second Thought
• Number is not prime if it has divisor other
than 1 and itself
• If number not divisible by 2, will not be
divisible by any even number
• Check for two, then only check odds
• Only have to check up to square root of n
Prime - Second Try
bool IsPrime(int n)
{
int i, limit;
if (n == 2) return true;
if (n % 2 == 0) return false;
limit = sqrt(n) + 1;
for (i = 3; i <= limit; i += 2)
if (n % i == 0) return false;
return true;
}
Efficiency Trade-off
• Recall implementations of IsPrime
• Final version more efficient
• Original is more readable and easier to
prove correct
• Principal concern must be correctness
• Secondary factors are efficiency, clarity,
and maintainability
• No “best” algorithm from all perspectives
GCD
• Greatest Common Divisor of two numbers
– largest number that divides evenly into both
• Function to determine GCD of two values
int GCD(int x, int y);
• e.g.
– GCD(49, 35) = 7
– GCD(6, 18) = 6
– GCD(32, 33) = 1
Brute Force GCD
int GCD(int x, int y)
{
int g = x;
while (x % g != 0 || y % g != 0)
{
g--;
}
return g;
}
Improved GCD
int GCD(int x, int y)
{
int g;
if (x < y) g = x; else g = y;
while (x % g != 0 || y % g != 0)
{
g--;
}
return g;
}
Problems with Brute Force
• Poor choice for efficiency
– e.g. GCD(10005, 10000) = 5
• Long running loop to find simple answer
• Can’t count up! Why?
• Other choices?
Euclid’s Algorithm for GCD
1. Divide x by y; call remainder r
2. If r is zero, answer is y.
3. If r is not zero,
set x equal to old value of y,
set y equal to r,
repeat entire process
• Difficult to prove correct
Euclid’s GCD
int GCD(int x, int y)
{
int r = x % y;
while (r != 0)
{
x = y;
y = r;
r = x % y;
}
return y;
}