1 of 10

COMPUTATIONAL THINKING

By

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 10

  • Problem:
  • Every integer can be expressed as a product of prime numbers. Design an algorithm to compute all the prime factors of an integer n.
  • Algorithm development:
  • Examination of our problem statement suggests that
  • n = f1xf2xf3x…xfk where n>1 and f1<=f2<=… <=fk
  • The elements f1, f2, f3,…, fk are all prime numbers. Applying this definition to some specific examples we get
  • 8 = 2x2x2
  • 12 = 2x2x3
  • 18 = 2x3x3
  • 20 = 2x2x5
  • 60 = 2x2x3x5

Dept of CSE

2025 - 26

COMPUTING THE PRIME FACTORS OF AN INTEGER

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 10

  • An approach to solving this factorization problem that immediately comes to mind is to start with the divisor 2 and repeatedly reduce n by a factor of n until 2 in no longer an exact divisor.
  • We then try 3 as a divisor and again repeat the reduction process and so on until n has been reduced to 1.
  • Consider the case when n = 60.
  • Marking with an asterisk the unsuccessful attempts to divide, we have

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 10

  • We can make several observations from this example.
  • Firstly, 2 is the only even number that we need to try.
  • In fact we pay careful attention to our original definition we will see that only prime numbers should be considered as candidate divisors.
  • Our present approach is going to test a lot of unnecessary divisors.
  • From this we can begin to see that generation of a set of prime numbers should be an integral part of our algorithm.
  • From our earlier work on primes and smallest divisors (algorithm 3.2 and 3.4) we know that all prime factors of n must be less than or equal to √n.
  • This suggests that we should perhaps produce a list of primes up to √n before going through the process of trying to establish the prime factors of n.

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 10

  • Further thought reveals that there is a flaw in this strategy which comes about because prime factors may occur in multiples in the factorization we are seeking.
  • A consequence of this is that in precomputing all the primes up to √n we may end up computing a lot more primes than are needed as divisors for the current problem. (As an extreme examples if n were 1024 we would calculate primes up to 32 whereas in fact the largest prime factor of 1024 is only 2.)
  • A better and more economical strategy is therefore to only compute prime divisors as they are needed.
  • For this purpose we can include a modified version of the sieve of Eratosthenes that we developed earlier.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 10

  • As in our earlier algorithm as soon as we have discovered n is prime we can terminate.
  • The top-level description of the central part of our algorithm is:

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 10

  • Each time we make the division:
  • n div nxtprime (e.g. 60 div 2)
  • We know the process must continue until the quotient q resulting from this division process is less than nxtprime.
  • At this point we will have:
  • (nxtprime)2 > n
  • Which will indicate that n is prime.
  • The conditions for it not yet being established that n is prime are therefore:

(a) exact division (i.e. r := n div nxtprime = 0)

(b) quotient greater than divisor (i.e. q:= n mod nxtprime>nxtprime)

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 10

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 10

  • Step 0: Start
  • Step 1: Read N
  • Step 2: Initialize nxtprime := 2
  • Step 3: q:= n div nxtprime
  • Step 4: r := n mod nxtprime
  • Step 5: Repeat Step 5.1 and 5.2 till q!=1
  • Step 5.1: if r = 0 then display ‘nxtprime as Prime factor’
  • Step 5.2: compute N := N / nxtprime
  • Step 5.1’: Otherwise Get ‘Next Prime’
  • Step 5.3: compute q:= n div nxtPrime
  • Step 6: If N > 1 then display N as Prime factor
  • Step 7: Stop

Dept of CSE

2025 - 26

Algorithm:

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 10

  • Notes on design
  • The computational cost for this algorithm can be divided into two parts.
  • The part for generating the prime divisors and the part for computing the prime factors.
  • Applications
  • Factoring numbers with up to six digits.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques