0
Please help me with this C program
Write a program to read an integer from user and output highest divisor of that integer that is also power of a prime number. Using only loops and conditionals.
2 Antworten
+ 2
An example says more than 1000 words. Basically you need to to factorization but you can cut some edges.
Let's start with the number 80.
number = 80;
maximum_factor_found = 1;
Now we more or less check all the factors up to 80, and all the powers. Starting at 2.
current_factor = 2;
current_power = current_factor;
if(current_factor divides number){
// we found a divisor!
// now we find the biggest power that still divides
while(current_power divides number){
current_power *= current_factor;
}
current_power /= current_factor;
// is it the biggest factor we have found yet?
if(current_power > maximum_factor_found)
maximum_factor_found = current_power;
// we don't need the factors of 2 anymore, so we divide them out.
number /= current_power;
}
What this doing is trying how often we can divide 2 into 80.
2 divides 80.
does 2*2 == 4 divide 80? yup!
does 2*2*2 == 8 divide 80? yup!
does 2*2*2*2 == 16 divide 80? yup!
does 2*2*2*2*2 == 32 divide 80? nope!
So we store 16 as the biggest prime-power-factor we have found so far.
We also set 80 / 16 == 5 as our new number. Then we repeat with 3, 4, and so on.
current_factor = 3;
current_power = current_factor;
And run the above loop again.
3 does not divide 5 though so there is nothing to do.
4 does not divide 5 and there is nothing to do.
5 divides 5, so there is something to do.
The highest power of 5 that fits into 5 is 5 which is not bigger than our maximum, 16, so our maximum stays 16.
We divide 5/5, and land on 1.
When we arrive at 1, we stop.
16 is the biggest prime-power factor of 80.
I hope that helps!
0
what is wrong with this code? it s giving runtime error.
#include<stdio.h>
#include<conio.h>
#include<math.h>
int main()
{
int n,i,j,k=0,g;
double a=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
int b=0;
for(j=1;j<=i/2;j++)
{
if(i%j==0)
{
b=1;
break;
}
}
if(b==0)
{
while(a<=n)
{
a=pow(i,k);
int r=a;
if(n%r==0)
g=r;
k++;
}
}
}
printf("%d",g);
return 0;
}