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

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    113

    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

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    I need prime factors.. that's the point.

  4. #4
    Registered User andrew89's Avatar
    Join Date
    Dec 2011
    Location
    Indiana, United States
    Posts
    80
    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.
    If, for some reason, I don't make any sense at all, it's highly likely that I've been up all night on some strange bender that isn't normal. I likely unarmed and far from dangerous. While I haven't been known to physically harm anyone or anything else, there have been unsubstantiated reports that I have driven others into both a hazy stupor as well as a blinding rage. Otherwise, I hope I helped.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    72
    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();
    }
    Last edited by rac1; 12-27-2011 at 08:46 AM.

  6. #6
    Registered User andrew89's Avatar
    Join Date
    Dec 2011
    Location
    Indiana, United States
    Posts
    80
    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.
    If, for some reason, I don't make any sense at all, it's highly likely that I've been up all night on some strange bender that isn't normal. I likely unarmed and far from dangerous. While I haven't been known to physically harm anyone or anything else, there have been unsubstantiated reports that I have driven others into both a hazy stupor as well as a blinding rage. Otherwise, I hope I helped.

  7. #7
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    Quote Originally Posted by andrew89 View Post
    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

  8. #8
    Registered User andrew89's Avatar
    Join Date
    Dec 2011
    Location
    Indiana, United States
    Posts
    80
    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?
    If, for some reason, I don't make any sense at all, it's highly likely that I've been up all night on some strange bender that isn't normal. I likely unarmed and far from dangerous. While I haven't been known to physically harm anyone or anything else, there have been unsubstantiated reports that I have driven others into both a hazy stupor as well as a blinding rage. Otherwise, I hope I helped.

  9. #9
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    Quote Originally Posted by andrew89 View Post
    Well... I imaging you know how to check if a number is prime,
    what does that mean..

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    @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.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 12-28-2011 at 01:52 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku brute force
    By snare91 in forum C++ Programming
    Replies: 8
    Last Post: 02-14-2011, 07:20 AM
  2. Brute Force
    By 123sample in forum C Programming
    Replies: 4
    Last Post: 09-12-2010, 12:37 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Brute Force
    By Wiz_Nil in forum C++ Programming
    Replies: 13
    Last Post: 02-15-2002, 01:28 PM
  5. Brute-Force
    By red11514 in forum C Programming
    Replies: 1
    Last Post: 11-13-2001, 12:53 AM

Tags for this Thread