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
This is a discussion on how to find factors of n! (No brute force) within the C Programming forums, part of the General Programming Boards category; How to find factors of a number (n!)^2. If its for N, its easy to solve.. but its like N! ...
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?
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"
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.
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.
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.
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.
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?
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.
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.
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"
@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.
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"