i have to find proper divisors of a positive integer.for instance,the proper divisor of 15 are 1,3,5.
input 15
output
1 3 5 like that.
Thank you for your helps.
whitech
- 4 Contributors
- forum5 Replies
- 7 Views
- 6 Years Discussion Span
- comment Latest Post by cse.avinash
whitech
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
int n,m,t;
printf("Enter a number:");
scanf("%d",n);
for(m=1;m<n;m++)
for(t=1;t<=m;t++)
{
n=m*t;
printf("%d,%d",m,n);
}
system("PAUSE");
return 0;
}
i wrote this codes but it doesnt work.can anyone help me?
D33wakar 36
you forgot to use '&' in your scanf statement.
scanf("%d",&n);
but what's the point of this
for(m=1;m<n;m++)
for(t=1;t<=m;t++)
{
n=m*t;
printf("%d,%d",m,n);
}
whitech
in last lesson we learnt the loops and we started with for so i tried to use the for loop.Probably its ridiculous :D i have to solve this problem.
Edited
by whitech: n/a
Adak 419
Step back from your keyboard for a sec and think about the area that needs to be searched. One is a divisor for every integer, so you can start with 2:
n1 is the first candidate divisor, n2 is the second candidate divorsor. Product is n1 * n2. Number is the number from the user, that you're trying to find the divisors for.
for(n1 = 2; ....
And there's no reason to continue searching above one-half of the number you're finding divisors for, because there's no number between 2 and 1 to go with it, if you get my drift.
so
for n1 equals 2 thru number/2;
//and you'll want to increment n1 of course
for(n1 equals 2; n1 less than or equal to number/2; n1++)
Now in the body of the for loop, you need to test if n1 * n2 == number, but we didn't say a thing about n2 yet!
n2 can start at number/2, and it can be decremented after every n1 is done testing it's loop. So you wind up with a nested pair of loops:
And when you're testing for divisors, there's no need to test if n1 * n2 is greater than the product, in the inner loop. Because the product only increases in the inner loop.
for(n2 equals number/2; n2 >= n1; decrement n2) {
for(n1 equals 2; product <= number; increment n1) {
product equals n1 times n2
Add a print line for n1 * n2 == product, so you can debug your program
if(product equals numbers) {
print it, n1 and n2 are divisors
}
}
}
Notes:
1) n2 >= n1 is not quite right. n2+1 >= n1 is needed for the last pair, when the divisors are equal: 4 * 4 = 16 for instance.
2) Odd numbers divided by 2 will lose one bit: 15/2 is 7. If it's an odd number, you need to add +1 to the n2 starting value of n2.
If you don't know how to use modulus operator yet, this is it:
if(number % 2 == 0) { //using modulus operator: %
//number is even
n2 = number/2;
}else {
//number is odd
n2 = number/2+1;
}
Otherwise, just add +1 to all the n2 starting numbers.
cse.avinash -1
Think of this:--
Q)Find all divisors of 80.
soln:-
all divisors of 80 are:- 1,2,4,5,8,10,16,20,40,80
notice the fact:--
it can be written as:--
L.H.S R.H.S
1 * 80
2 * 40
4 * 20
5 * 16
8 * 10
notice LHS elements are less than 9.
i.e., sqrt(80)=8.xxx equivalent to 9.
it you find only the divisors before 9 divisors after 9 will come automatically..
Use this concept, and this will decrease the time complexity to a great extent for a large range of numbers. :)
Edited
by cse.avinash: n/a