CODEWITHSUNDEEP
algorithmfactorialfactorization
KawaiKx
KawaiKx

Reputation: 9920

largest factorial number present as a factor in some integer n

I am working on designing an algorithm to find the largest factorial number present as a factor in some integer n. This problem is given in "How to solve it by computer" by R.G.Dormey. could you help me in how to go about designing algorithm.. answer has to be a factor of the integer n and also a factorial number..

solution I thought of:

first confirm that integer is not prime. if prime, no further solution posible..

if not prime, find out the largest factor of the integer

check if it is a factorial number or not..

if yes, that is the answer

if not, find out second largest factor of the integer..

check if it is a factorial number or not...

and so on..

Upvotes: 1

Views: 3181

Answers (5)

lokesh5790
lokesh5790

Reputation: 62

#include<stdio.h>
main()
{
      int i,n;
      scanf("%d",&n);
      for(i=2;n>1&&n%i==0;i++)
      n/=i;
      printf("%d",i-1);
}

n is the input number

Upvotes: 0

abhishek.konweb
abhishek.konweb

Reputation: 1

long prod = 1;
long maxFactor = 1;

for(long i=2; i<=n && prod< n && n%i==0 ;i++){

    prod  = prod*i;
    if(n%prod == 0) maxFactor = prod;
}

Here n is the number whose largest factorial factor we need to find out and the final value of macFactor is the final solution.

Note: Factors of factor of a number are also the factors of the number.

If the factor is a factorial value then it must the product of the consecutive integers starting from 1 (in other words it should be the product of its factors other than itself)

Upvotes: 0

borrible
borrible

Reputation: 17366

You're looking to find the largest factorial that goes into your integer, so you just need to steadily increase your factors. I.e. Check to see if the resulting integer is divisible by 2, 3, 4, etc... The first time you get a failure you know that no larger factorial will divide your integer. E.g. if your integer is divisible by 2 ... 6 but not 7, you know the answer is 6!.

Upvotes: 2

jemmanuel
jemmanuel

Reputation: 476

given the property of factorials to grow very very large very fast...i would be tempted to try dividing it directly. first find the largest factorial less than your number...then start checking by dividing eg: let N be your number. Let factorial f(fac,num) be your factorial function which returns a factorial less than your number. such that num! = fac Then do the following:

Check if (N % fac)==0; else try (N*num) % fac then (N* (num)*(num-1)) % fac

the answer u require is (num) in first case (num-1) in second case and so on

Upvotes: 0

Dennis Crane
Dennis Crane

Reputation: 461

Divide N by 1, then the result by 2, then the result by 3,... then by k+1. Once there is no integer result for k+1, k! is an answer.

Upvotes: 4

Related Questions