The greatest common divisor
- The greatest common divisor
(GCD) of the two integers
x and
y is:
- The largest integer number
that is divisor of
both x and
y
|
- Examples:
GCD(4,2) = 2
GCD(5,7) = 1
GCD(24,36) = 12
|
- Exercise:
- Write a
Java program that
reads in 2
integer numbers
x and
y and
prints their
GCD
|
|
The greatest common divisor
- Develop a
plan:
How would you find:
GCD(372, 930) ?
|
|
The greatest common divisor
- Develop a
plan:
How would you find:
GCD(372, 930) ?
Try 1: 372%1 == 0 930%1 == 0 --> 1 is common divisor => GCD = 1
Try 2: 372%2 == 0 930%2 == 0 --> 2 is better divisor => GCD = 2
Try 3: 372%3 == 0 930%3 == 0 --> 3 is better divisor => GCD = 3
Try 4: 372%4 == 0 930%4 == 2 --> 4 is not a common divisor
Try 5: 372%5 == 2 930%5 == 0 --> 5 is not a common divisor
Try 3: 372%6 == 0 930%6 == 0 --> 3 is better divisor => GCD = 6
and so on...
When do we stop ???
|
|
The greatest common divisor
- Develop a
plan:
How would you find:
GCD(372, 930) ?
Try 1: 372%1 == 0 930%1 == 0 --> 1 is common divisor => GCD = 1
Try 2: 372%2 == 0 930%2 == 0 --> 2 is better divisor => GCD = 2
Try 3: 372%3 == 0 930%3 == 0 --> 3 is better divisor => GCD = 3
Try 4: 372%4 == 0 930%4 == 2 --> 4 is not a common divisor
Try 5: 372%5 == 2 930%5 == 0 --> 5 is not a common divisor
Try 3: 372%6 == 0 930%6 == 0 --> 3 is better divisor => GCD = 6
and so on...
When do we stop ??? min(372,930)
===> We have a plan !
|
|
The greatest common divisor
- Write out the
steps of the
plan:
read in x
read in y
GCD = 1; // This is the "best" GCD we have so far
min = min(x,y)
for ( k = 2, 3, 4, 5, ... min )
{
if ( k is divisor of x and y )
GCD = k; // We found a better GCD
}
|
|
The greatest common divisor
- Translate the
steps of
the plan to
Java code:
Scanner input = new Scanner(System.in);
int x = input.nextInt();
int y = input.nextInt();
int k, min;
int GCD = 1; // Best GCD so far
min = (x < y) ? x : y;
for ( k = 2; k <= min; k++ )
{
if ( (x%k == 0) && (y%k == 0) )
GCD = k; // We found a better GCD
}
System.out.println(GCD);
|
|
DEMO:
demo/05-loops/05-algorithms/GCD.java
Step in
BlueJ (use 8 and 12)
Factoring an integer number
- Fact from
Mathematics:
- Every integer number can
be
factored into
its
prime number
factors
|
- Prime number
factors of
the number
x:
- Are the
prime numbers whose
product is
equal to
the number
x
|
- Example:
The prime factors of 6 are: 2 3 (2 × 3 = 6)
The prime factors of 12 are: 2 2 3 (2 × 2 × 3 = 12)
The prime factors of 90 are: 2 3 3 5 (2 × 3 × 3 × 5 = 90)
|
- Exercise:
- Write a Java program that
reads in an
integer number and
prints out its
prime factors
|
|
Factoring an integer number
- Develop a
plan:
How do you factor the number 90 ?:
90 = ???
|
|
Factoring an integer number
- This is how
you have be taught
to factor a
number:
How do you factor the number 90 ?:
90 = ???
(1) Try dividing by 2: 90%2 == 0 --> 2 is a factor
90/2 = 45 ===> next: factor 45
(2) Try dividing by 2: 45%2 == 1 --> no more 2's, try next factor
(3) Try dividing by 3: 45%3 == 0 --> 3 is a factor
45/3 = 15 ===> next: factor 15
(4) Try dividing by 3: 15%3 == 0 --> 3 is a factor
15/3 = 5 ===> next: factor 5
(5) Try dividing by 3: 5%3 == 3 --> no more 3's, try next factor
(6) Try dividing by 4: 5%4 == 1 --> no more 4's, try next factor
(7) Try dividing by 5: 5%5 == 0 --> 5 is a factor
5/5 = 1 ===> 1 cannot be factored any further -- STOP
|
|
Factoring an integer number
- Write out the
steps of
the plan:
number = input.nextInt(); // Read in input
nextFactor = 2; // Smallest prime number factor
as long as ( number != 1 ) // Number can be factored further...
{
if ( number is divisible by nextFactor )
{
print nextFactor; // Found another prime factor
reduce number to number/nextFactor
}
else
{
try the next factor
}
}
|
|
Factoring an integer number
- Translate the
steps of
the plan to
Java code:
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int number = input.nextInt();
int nextFactor = 2;
while ( number != 1 )
{
if ( number%nextFactor == 0 )
{
System.out.println(nextFactor);
number = number/nextFactor;
}
else
{
nextFactor = nextFactor+1;
}
}
}
|
|
DEMO:
demo/05-loops/05-algorithms/PrimeFactor.java
Step in
BlueJ (use 126 = 2*3*3*7)
Perfect numbers
-
Perfect numbers:
- A number
x is
perfect if:
- The sum of its
factors is
equal to
the number
itself
(= x)
|
|
- Examples:
6 is a perfect number because:
Factors of 6 are: 1 2 3
Their sum: 1 + 2 + 3 = 6
28 is a perfect number because:
Factors of 28 are: 1 2 4 7 14
Their sum: 1 + 2 + 4 + 7 + 14 = 28
The 3rd and 4th perfect numbers are: 496 and 8128
|
|
Checking
if a number is perfect
- Programming exercise:
- Write a
Java program that
read in a
number and
prints out
whether the input number
is a perfect number
|
- Plan:
x = read input
for each number i = 1, 2, 3, ...., x-1
Check if i is a divisor of x
If i is a divisor, add i to sum
if ( sum == x )
print "is a perfect number"
else
print "is not a perfect number"
|
|
Checking
if a number is perfect
- Programming exercise:
- Write a
Java program that
read in a
number and
prints out
whether the input number
is a perfect number
|
- Java program:
Scanner input = new Scanner(System.in);
int x, sum, i;
x = input.nextInt();
sum = 0;
for ( i = 1; i < x; i++ )
if ( x%i == 0 ) // i is a divisor of x
sum = sum + i; // Add i to sum
if ( sum == x )
System.out.println("is a perfect number");
else
System.out.println("is not a perfect number");
|
|
DEMO:
demo/05-loops/05-algorithms/PerfectNumber.java
❮
❯