COMPUTATIONAL THINKING

By

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

_{PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY}

• Problem:
• Given an integer n devise an algorithm that will find its smallest exact divisor other than one.
• Algorithm development
• Approach 1: (Not an Efficient Approach)
• We can take the set of numbers 2, 3, 4, . . ., n and divide each one in turn into n.
• As soon as we encounter a number in the set exactly divides into n our algorithm can terminate as we must found the smallest exact divisor of n.

Dept of CSE

Friday, January 13, 2023

THE SMALLEST DIVISOR OF AN INTEGER

PVPSIT (Autonomous)

Problem Solving Techniques

• However, is can we design a more efficient algorithm?
• As a starting point of investigation, let us work out and examine the complete set of divisors for some particular number.
• Example: number is 36
• The complete set of divisors is (except 1 and itself):

​

• We know that an exact divisor of a number divides into that number leaving no remainder.
• For the exact divisor 4 of 36, we have:

​

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

• That is, there are exactly 9 fours in 36.
• It also follows that the bigger number also divides exactly into 36.
• That is,

​

​

​

​

• Similarly, if we choose the divisor 3, we find that it tells us that there is a bigger number 12 that is also an exact divisor of 36.

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

​

​

• Our algorithm can safely terminate when we have a pair of factors that correspond to
• (a) the biggest smaller factor s,
• (b) the smallest bigger factor b.

​

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

• Realization from Approach 1
• It follows that it is not necessary to look for smallest divisors of n that are greater than square root of n.
• This consideration is particularly relevant if we are likely to have to deal with large prime numbers.
• Approach 2 (An Efficient Approach)
• If this square root limit allows us to stop the search for a valid exact divisor much earlier.

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

• Before satisfied with our new design (square root(n)), once check is there any improvements?
• Example: number is 127
• The divisors we would consider are
• 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
• We know that all even numbers are divisible by 2.
• If the number we are testing is odd, we need only odd numbers as divisors. (i.e. 3, 5, 7, 9, . . .)

​

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

​

​

​

​

​

​

• All that is left to do now is work out the implementation details.
• The divisors to test can be generated by starting d at 3 and using

d := d+2

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

• If n mod d=0 then d is an exact divisor of n.
• Our algorithm may terminate when either or both of the conditions n mod d=0 and d>=r are met.

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

• Step 0: Start
• Step 1: Read N
• Step 2: If N mod 2 = 0 then Display “2” as Answer and go to Step 7.
• Step 3: Compute r := sqrt(N)
• Step 4: Initialize d := 3
• Step 5: Repeat Step 5.1 till (N mod d != 0 and d < r)
• Step 5.1: d:= d+2
• Step 6: If N mod d = 0 then Display “d” as result otherwise Display “1” as result.
• Step 7: Stop

​

Dept of CSE

Friday, January 13, 2023

Algorithm

PVPSIT (Autonomous)

Problem Solving Techniques

• Applications:
• Allocation problems.

Dept of CSE

Friday, January 13, 2023

PVPSIT (Autonomous)

Problem Solving Techniques