## Thursday, 3 July 2014

### How to Find prime factor of a number

Find Prime factor of a number is one of most common question  encounter in basic mathematics . But it has very high uses not only in mathematics problems but also in high level algorithmic programming problems. Mostly problems that uses properties of numbers .
If you wan't to become a programmer ,you will face many problems that uses properties of numbers , and we know a good programmer always try to find best way to solve problem otherwise there is always a straight way (Brute force way ) to solve almost any problem .
But we know it will ruin speed of  programming  result  that's why we always try to find fastest and effective way to solve problems .

### Algorithm to Find prime factor of a number :

It uses very basic concept of division

1. Let number is n
2. Set encounter to 2 (i.e i=2)
3. Now divide n by i
If  n is divisible by i  :- put it in list or array let say it pf
then update value of n by n/i (n = n/i)
then go to step 3 again
Else :- continue
1. Now check if  i > squire root of n :-then stop iterating and exit
2. Else : increment counter by 1 ( i = i+1) and goto step 3

### Python Program to Find prime factor of a number :

1. # Find prime factor of a number
2. # http://beginer2cs.blogspot.com
3. # Python 2.7
4. import math
5. def prime_fact(n):
6.     '''
7.        return a list ,contain prime factor of n
8.    '''
9.     flag=True # we Use this to continue or come out from while loop
10.     pf=[]
11.     i=2 # we start iteration from 2 (just as an counter)
12.     sq = math.sqrt(n) # this is end point of iteration ( Think why ??)
13.
14.     while(flag)#start iteration
15.         if n%i == 0#if i is  factor of n
16.             pf.append(i) #then append it in list
17.             n=n/i  #and update value of n by n/i
18.
19.         elif i>sq : #test for end of iteration
20.             flag =False
21.
22.         else:
23.             i = i+1 # increment counter by 1
24.     return pf
25. if __name__=='__main__':
26.     n=int(raw_input('Enter ur number : '))
27.     print prime_fact(n)

Output :

THANKS FOR UR GREAT COMMENT

Blogger Widgets