a) Describe a procedure for finding the prime

Solution:

Step 1:

a)In this problem we need to describe a procedure for finding the prime factorization of an integer.

We know that every integer has a prime factorization.

Let us consider , n is an integer and p is aprime number.

If n has no prime factors not exceeding is found, then n is a prime number.

If n has a prime factor , then a prime factor p not exceeding  will be found , then continue by factoring  . Note that  has no prime factors less than p.

Again if  has no prime factor not exceeding  is found, then  is a prime number.Otherwise if it has a prime factor q not exceeding  will be found, then continue by factoring . Note that  has no prime factors less than q.This procedure will continued until the factorization has been reduced to a prime number.