Wednesday, 25 March 2015

Largest Prime Divisor of a Number

Problem Statement :
Prime factors of 830297 are  13 and 17.
Here 17 is largest prim divisor

What is the largest prime factor of the number 580851475758 ?

Prequisite :

• You must need To know Fastest way to check a number is Prime or Not. (Play-with-prime)
• Concept of factorization

We know all numbers can be factorize in term of prime numbers. we gonna use this Property to solve this problem

How we gonna solve this problem lets Solve By an Example

• Need to factories 830297
• 830297 is divisible by 13 so now you'll test with 830297 / 13 = 63869
• 3869 is still divisible by 13, you are at 4913
• 913 doesn't divide by 13, next prime is 17 which divides 4913 to get 289
• 289 is still a multiple of 17,  :> 289/17 =17 Now you have 17 which is the divisor and stop.

C Program To find Largest Prime Factor

1. //https://beginer2cs.blogspot.com
2. //C Program to find Largest Prime Factor of given Number
3. #include<stdio.h>
4. #include<math.h>
5. int isPrime(int n){
6.         int i,sqrt_n,flag=1;
7.
8.
9.                 sqrt_n=(int)sqrt(n); //squire root of n
10.                 sqrt_n++; //approximating sqrt
11.         if(n<2){
12.                 return 0; //return False
13.         }
14.         else{
15.                 if(n==2){
16.                         return 1; //return True
17.                 }
18.                 else if(n%2==0)
19.                         return 0;
20.         }
21.         for(i=3;i<sqrt_n;i=i+2){
22.                 if(n%i==0){
23.                         flag=0;
24.                         break;
25.                 }
26.         }
27.         return flag; //return value of flag 0(false) or 1(true)
28. }
29. main(){
30.     long long int n;
31.     long int i;
32.     printf("Enter Number : ")
33.     scanf("%d",&n);
34.     i=2;\
35.      //Finding Largest Prime factor
36.     while(1){ //While True
37.         if(isPrime(i)){
38.                 while(1){
39.                         if(n%i==0 && n>i)
40.                                 n=n/i;
41.                         else
42.                            i++;
43.                            break;
44.                         }
45.                 }
46.                 else
47.                    i++;
48.                 if(n==i)
49.                    break;
50.         }
51.         printf("largest Prime Factor = %d\n ",i);
52. }

Please Suggest If you found Any Bug or you know better approach to solve it .
Thank You