The way i see it this problem is a bit more complicated.
Say, for example the given no. is X = 2^3 * 3^5 ... Now if we want to
reduce X in the form M^N where both M and N 1 then its not possible.
Hence, the actual problem reduces to finding not only the prime
factors but actual prime
Hello Sid
Your code is working for N=4,8 but failing when N=9
9 is expressed as 3^2 but your code is giving output as :Not possible.
On Dec 26, 9:36 pm, sid1 siddhantkhann...@gmail.com wrote:
This algorithm won't work as primes might have different power. for
eg. N=12
12 is divisible by 2
considering number to be a 32 number(also applicable in the same way to 64 bit)
one possibility is
let x be the number
find log10x
for 32 bit numbers max value of n is 64
so for n = 1 to 64
find p = logx10/n
take antilog and take nearest integer as m
m = 10^p;
again find m^n
if it is equal to x
@Sid small Modification in ur code in 3rd line it should be float ans
= log(n)/log(i); instead of float ans = log(n)/log(2);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I think u hav misunderstood my logic .
I told What comes to my mind is to get all PRIME FACTORS from 2 to
SQRT(N) [Prime Sieve] , Here N is the Given Integer .
So I wrote the code and let me know if there is any problem :-
#includecstdio
#includeiostream
#includecmath
using namespace
Continued:--
Sry , I misunderstood the problm I thought it to be the power of Prime
factor ...
For finding the required answer of N can be done N = a^p b^q
Need to find the hcf of (p,q,...) 1 then the number can be
expressed as m^n ..
--
You received this message because you are
@ SAmmm
Also i would like to mention that we don't need to explicitly
calculate all the primes...All we need to do is cancel out the factors
and keep track of the powers..
On Dec 26, 11:43 pm, SAMMM somnath.nit...@gmail.com wrote:
Continued:--
Sry , I misunderstood the problm I thought it to
I know tht it need GCD(a,b,) where N = p^a q^b...
I wrote it previously ... it's just tht my lates reply is not in
sequence . I hav added tht later ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@Sammm
I have jolted down the code in my previous post... Have a look.. it
works on the GCD basis..
On Dec 26, 11:43 pm, SAMMM somnath.nit...@gmail.com wrote:
Continued:--
Sry , I misunderstood the problm I thought it to be the power of Prime
factor ...
For finding the required answer of N
@Sammm Yes you are correct. I wrote 2 by mistake.
it should be i. because (log n)/log i = log n to the base i. So if i^m
= n
=log n to the base i = integer.
@Lucifer I think that your approach is the best optimized. My algo is
testing all the numbers while yours uses only prime factors of N.
On
From Wht I can understand from problm to check whether N can be
expressed a m^n : Eg: 1331=11^3
What comes to my mind is to get all prime factors from 2 to SQRT(N)
[Prime Sieve] , Here N is the Given Integer .
Now Iterate over the prime number(p) from 2 to Sqrt(N)
do
T=N;
if(!(T%p))
This algorithm won't work as primes might have different power. for
eg. N=12
12 is divisible by 2 so it ends up being 3. then 3 divides by 3. So it
prints possible. But the actual answer is no.
Correct code:
for (int i=2;i=sqrt(n);i++)
{
float ans = log(n)/log(2);
int an = ans;
if
Hello Samm
I got your approach
It seems it is not working for some of the examples
Eg: N = 6
6 = 2X3 = 1X6 and hence it is not possible
but your code prints Yes possible.
On Dec 26, 9:03 pm, SAMMM somnath.nit...@gmail.com wrote:
From Wht I can understand from problm to check whether N can
13 matches
Mail list logo