College of Computer Studies

Algorithm
(CC0007)

<Machine Problem 1>

Submitted by:

1X1
PICTURE

LN, FN, MI

Submitted to:

<______________________>
Professor

Date of submission

1
I. PROGRAM OUTCOME/S (PO) ADDRESSED BY THE LABORATORY EXERCISE
● Apply knowledge of computing appropriate to the discipline [PO: A]

II. COURSE LEARNING OUTCOME/S (CLO) ADDRESSED BY THE LABORATORY EXERCISE

● To understand and apply knowledge of computing concepts and fundamentals. [CLO: 1]

III. INTENDED LEARNING OUTCOME/S OF THE LABORATORY EXERCISE

At the end of this exercise, students must be able to:

● Solve the given problem

● Create documentation base on the given problem
● Create test cases for the problem

2
Problem 1

Create a program that calculates the Greatest Common Divisor (GCD) of two given non-negative integers
using the Euclidean algorithm. The program should take two integers as input and display each step of
the algorithm, finally printing out the GCD of the two numbers.

The Euclidean algorithm for finding the GCD of two integers is based on the principle that the GCD of
two numbers also divides their difference. To compute the GCD of two integers a and b, where a > b,
divide a by b. If the remainder r is 0, then b is the GCD. Otherwise, repeat the process with b and r.

Functional Requirements:

The program should prompt the user to enter two non-negative integers.

The program should validate the input to ensure that two integers are provided and that they are non-
negative.

The program should implement the Euclidean algorithm to find the GCD:

a. Divide the larger number by the smaller number.

b. Take the remainder and divide the smaller number by this remainder.

c. Continue this process iteratively until the remainder is 0.

d. The last non-zero remainder is the GCD of the two numbers.

The program should display each step of the division process, including the quotient and the remainder.

The program should output the GCD of the two integers once it is found.

Sample Output:

For the input "10 45", the program should output:

Calculating GCD of 10 and 45 step by step:

10 = 45 * (0) + 10
45 = 10 * (4) + 5
10 = 5 * (2) + 0

The GCD of 10 and 45 is 5

And for the input "1701 3768", the program should output:

Calculating GCD of 1701 and 3768 step by step:

3
1701 = 3768 * (0) + 1701
3768 = 1701 * (2) + 366
1701 = 366 * (4) + 237
366 = 237 * (1) + 129
237 = 129 * (1) + 108
129 = 108 * (1) + 21
108 = 21 * (5) + 3
21 = 3 * (7) + 0
The GCD of 1701 and 3768 is 3

The program should be user-friendly, prompting the user for inputs and clearly displaying the output. It
should also handle edge cases, such as when one of the integers is zero.

Paste your program codes here together with screenshots of the output (3 different inputs and output),
write an explanation of how you have answered the problem, and list down your difficulties and
learnings in the machine problem.

1. Approach:

- Implemented the Euclidean Algorithm for finding the Greatest Common Divisor (GCD) of two
integers.

- Utilized a while loop to iteratively calculate remainders until reaching a quotient of 0.

- Printed each step of the calculation, illustrating the process.

2. Learning Outcome:

- Enhanced understanding of the Euclidean Algorithm.

- Improved familiarity with basic C++ syntax for functions, loops, and output.

3. Difficulties:

- Initially struggled with tracking and updating variables within the loop.

- Overcame challenges by carefully managing temporary variables and reassigned values.

4
Problem 2

Develop a program that generates a list of prime numbers up to a user-specified maximum number,
which should not exceed 100. The program must use the Sieve of Eratosthenes algorithm to identify and
list all prime numbers within the given range. Additionally, the program should visually represent the
sieving process by marking non-prime numbers with an 'X' and displaying the remaining prime numbers.

Functional Requirements:

The program should prompt the user to enter a maximum number, ensuring that it is a positive integer
and does not exceed 100.

Implement the Sieve of Eratosthenes algorithm to find all prime numbers up to the given maximum:

Initialize a list of numbers starting from 2 up to the entered maximum number.

Iteratively mark the multiples of each prime number starting from 2 as non-prime.

Continue the process until all non-prime numbers are marked.

The program should visually display the process of marking non-prime numbers with 'X' after each step
of the algorithm.

Once the algorithm is complete, the program should display the list of unmarked numbers, which are
the prime numbers up to the specified maximum.

The output should be formatted to display the numbers in a grid-like structure, as shown in the provided
image, and then list the prime numbers found.

Sample Output:

For the input "20", the program should output a grid showing the sieving process, marking non-primes
with 'X', followed by:

List of prime numbers up to 20:

2 3 5 7 11 13 17 19

For the input "100", the program should output a similar grid for numbers up to 100, followed by:

List of prime numbers up to 100:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

5
Non-Functional Requirements:

The program should be user-friendly, with clear prompts and instructions.

The grid and prime number listing should be easy to read and well-formatted.

The program should handle invalid inputs gracefully, providing the user with appropriate feedback.

The purpose of this program is to not only list primes but also to teach or demonstrate the Sieve of
Eratosthenes method interactively and visually.

Paste your program codes here together with screenshots of the output (3 different inputs and output),
write an explanation of how you have answered the problem, and list down your difficulties and
learnings in the machine problem.

Enter the maximum number (up to 100): 20

2 3 X 5 X 7 X X X

11 X 13 X X X 17 X 19 X

List of prime numbers up to 20:

2 3 5 7 11 13 17 19

Enter the maximum number (up to 100): 100

2 3 X 5 X 7 X X X

11 X 13 X X X 17 X 19 X

X X 23 X X X X X 29 X

31 X X X X X 37 X X X

41 X 43 X X X 47 X X X

X X 53 X X X X X 59 X

61 X X X X X 67 X X X

71 X 73 X X X X X 79 X

X X 83 X X X X X 89 X

X X X X X X 97 X X X

List of prime numbers up to 100:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

6
1. Approach:

- Implemented the Sieve of Eratosthenes algorithm to find prime numbers up to a specified maximum.

- Created a boolean vector to mark numbers as prime or non-prime.

- Displayed the results in a grid format and listed prime numbers.

2. Learning Outcome:

- Deepened understanding of algorithms for finding prime numbers.

- Gained proficiency in using vectors and conditional statements in C++.

3. Difficulties:

- Faced challenges with array manipulation and indexing during the sieve algorithm.

- Overcame difficulties by carefully tracking indices and adjusting loop parameters.

Rubrics
The following rubrics/metrics will be used to grade students’ output in the lab exercise.

7
Program (50 pts) (Excellent) (Good) (Fair) (Poor)

Program execution Program executes Program executes Program executes Program does not
and correct correctly with no with less than 3 with more than 3 execute (10 – 11)
simulation(20pts) syntax or runtime errors (15 – 17 ) errors (12 – 14)
errors (18 – 20)

Correct output Program displays Output has minor Output has Output is incorrect
correct output errors (15 – 17) multiple errors (12 (10 - 11)
(20pts) with no errors (18 – 14 )
– 20)

Design of output Program displays Program displays Program does not Output is poorly
more than minimally display the designed (5)
(10pts) expected output required output
expected (10)
(8 – 9) (6-7)

Design of logic and Program is Program has slight Program has Program is
Algorithm logically well logic errors that significant logic incorrect (10 - 11)
designed (18 – 20) do no significantly errors (12 – 14 )
(20pts) affect the results
(15 – 17)

Standards Program is Few inappropriate Several Program is poorly

stylistically well design choices inappropriate written (10 - 11)
(20pts) designed (18 – 20) (i.e. poor variable design choices
names, improper (i.e. poor variable
indentation) (15 – names, improper
17) indentation) (12 –
14 )

Delivery The program was The program was The code was The code was
delivered on time. delivered within a within 2 weeks of more than 2 weeks
(10pts) (10) week of the due the due date. (6 – overdue (5)
date. (8 – 9) 7)