how to find factors of n! (No brute force)

How to find factors of a number (n!)^2.

If its for N, its easy to solve.. but its like N! ^ 2.. I am worried. Brute force wouldn't work here. so, how to solve??

got any idea? please post it

The very definition of the factorial function tells you exactly what the factors are. e.g. 5! = 5*4*3*2*1
Then you simply need to make use of x^2 being the same as x*x, and you'll realise that you just have the same list of factors twice.
Do you need prime factors or all factors?

I need prime factors.. that's the point.

Well... a prime number is any number that isn't divisible by any number than itself. So once you find a factor or whatever it is you're looking for up there ^^^ you add a bit to check if that number is prime.

this program is finding the dividers of an integer, i hope you can understand it and change it to N!^2

Code:

---

#include <stdio.h>




int p(int asal)
{
int y=1;


int i4;
  for(i4=2;i4<asal;i4++)
    {
      if (asal%i4==0)
          {
            y=0;
          }
    }
    return y;
}




int main()
{
 int x,i,ix=0,i1,i2,r,k,t;
 int f=0;
 int c[100];
 int d[100];
 int a=1;
int si=0;
int cntr=0;
int kontrol=1;


for(i1=0;i1<=50;i1++) c[i1]=0;


printf("enter a number to learn prime or not:");
scanf("%d",&r);




for(i1=0;i1<=100;i1++)
{
    c[i1]=0;
}
x=r;
for(i=2;i<=x;)
{
    si=si+1;
    if(si%20==0) i++;


  if ((x%i==0)&&(p(i)==1))
  {
    c[f]=i;
    f++;
    x=x/i;


  }
  else
  {
  i++;
  x=r;
  }
}
printf("\ntam bolenleri:");


for(i2=0;i2<=99;i2++)
{


    if ((c[i2]>1))
    {
    d[ix]=c[i2];
    printf(" %d, ",d[ix]);
    cntr++;
    ix++;
    }
}
for(i=0;i<cntr;i++)
{
    i2=i+1;
    for( ;i2<cntr;i2++)
    {
      if (d[i]==d[i2]){
      kontrol=0;
      }
      else
      kontrol*=1;
    }
}
if (kontrol==1)
      printf("\nthere isn't any same prime number dividers");
      else
      printf("\ntthere are same prime number dividers");


      printf("\n\nCoded By Thomas...");
getche();
}

---

You're really confusing. What is (n!)^2? Is that any number to the second power? Any number XOR'ed to the second power? Then you start talking about brute force and prime numbers. Can you sum up EXACTLY what you're trying to accomplish?

As far as I can tell, you're trying to get the factors of a number, and test and see if they are prime or not.

Quote:

---

Originally Posted by andrew89

You're really confusing. What is (n!)^2? Is that any number to the second power? Any number XOR'ed to the second power? Then you start talking about brute force and prime numbers. Can you sum up EXACTLY what you're trying to accomplish?

---

Actually, what I've said you is a part of program... sorry for not disclosing everything.
The mathematical analysis for the puzzle ends at finding number of positive integral factors of (n!)^2 [ read as N factorial square ] .. Its a number to second power.

So, the answer for number of positive solutions would be ( factors( n! ^ 2) + 1 ) / 2
but the issue I am facing is to find the prime factors .. As n! itself would be huge, n! ^ 2 would be "Can't Imagine".. ex: take n = 1235.. n! itself goes too big. [ These are the numbers I got to deal with. max range of n = 10^6 ].

So, how could I do that... Its pretty well understood that I can't solve in brute force way.
I can't even use external lib. - I mean I shouldn't

Well... I imaging you know how to check if a number is prime, as for the range--which as I understand the situation is what you have a problem with--then you only need to check numbers between 2 and the square root of the number being checked. Or is that still a problem?

Quote:

---

Originally Posted by andrew89

Well... I imaging you know how to check if a number is prime,

---

what does that mean..

Assuming ! means factorial and ^ means "to the power of",
given your formula n!^2 and n = 4 you get:
(2*3*4)*(2*3*4)
If a factor is not prime, you will have to compute its prime factors, like this:
(2*3*(2*2))*(2*3*(2*2))
You would probably want to collect the factors together and display it like this:
2*2*2*2*2*2*3*3
or better yet this:
2^6 * 3^2

First try making a program to show the prime factors for n.
After that, it will be fairly easy to extend it to n!^2.

Well the prime factors of (n!)^2 are the prime numbers in 1..n.
Unless you have to record their frequency then you only have to solve that. The rest is a red-herring.

@iMalc... could you tell me more about this frequency method.

@Andrew: Whether its n! or n! ^ 2.. as long as n value is high..
Its not a good approach to iterate all values from 1 to n if n = 12354 or similar big numbers.

Well if you need their frequency then you need to break down all factors into the prime factors and keep track of how many times each appears.
Lets try it with an example. How about (9!)^2:

That's equal to (1*2*3*4*5*6*7*8*9)^2
This expands to (1*2*3*4*5*6*7*8*9)*(1*2*3*4*5*6*7*8*9) but lets ignore the 1's and the duplicates for now and just concentrate only on 2 .. 9 and then double ther frequencies later.
Now we need to break those down into their prime factors: 2*3*(2*2)*5*(2*3)*7*(2*2*2)*(3*3)
Now we count how often each occurs: There are seven 2s, four 3s, one 5, and one 7.
Double the number of primes to take the square into account ane we get our answer of:

Fourteen 2s, eight 3s, two 5s, and two 7s.

And if you didn't need the frequencies then the answers are just the primes <= 9, which ignoring the above we can immediately see that these are 2, 3, 5, & 7 and low and behold these are what we found above doing it the long way to get the frequencies.