# Find factors of a number

I am a beginner in C. I have just written this program to find the factors of a provided number $n$ where $1\leq n \leq 10^9$. However, when I input large numbers (e.g. the maximum, $10^9$), the program takes a long time to finish finding the larger factors. How do I reduce its time taken? Also, are there any possible improvements for this code?

#include<stdio.h>
int main(){
int a,i;
scanf("%d",&a);
for(i=1;i<(a/2+1);i++){
if(a%i==0){
printf("%d\n",i);
}
}
printf("%d\n",a);
return 0;
}

• You can skip "1" since 1, after 2 you can skip all even numbers. Commented May 16, 2017 at 14:18
• @pacmaninbw you can only skip all even numbers if you want to find the prime factors. If you actually want all factors, you still need them. Commented May 16, 2017 at 14:22
• It may be worthwhile to perform the prime factorization; then all the factors can be constructed by combining those primes. That's starting to get too large for a comment, though! Commented May 16, 2017 at 16:39
• A quick observation that's too small for an answer - please don't get the bad habit of ignoring the return value from scanf()! Commented May 16, 2017 at 16:42
• What do you mean by the return value? @TobySpeight
– 54D
Commented May 16, 2017 at 16:45

You should realize that if $i$ is a divisor of $a$, then so is $a / i$. This way you get two divisors per found divisor.

In the same vein, you only need to search up to $\sqrt{n}$, because all factors above that have already been found as the second divisor.

#include <stdio.h>
#include <math.h>

int main(){
int a,i;
scanf("%d",&a);
int bound = ceil(sqrt(a));
for(i=1; i <= bound; i++) {
if(a%i==0) {
printf("%d\n",i);
if(a/i != i) printf("%d\n", a/i);
}
}
printf("%d\n",a);
return 0;
}

• Is there any way to list the factors in ascending order? This definitely runs much quicker but it isn't listed in order.
– 54D
Commented May 16, 2017 at 14:27
• @54D I'm pretty sure it is possible, but I don't know enough C to answer that. You would probably have to add the a/i numbers to some kind of buffer which you then work through after the main loop... Commented May 16, 2017 at 15:01
• @54D Also, you never said they should be in order in your question :) Commented May 16, 2017 at 15:02
• I realized, sorry about that ^^|| I'll mark this as accepted anyway, because it directly answers the question.
– 54D
Commented May 16, 2017 at 16:07
• Yes, that's right (and that's the trade-off against storage - I'd use the storage, FWIW). It's still much fewer tests than the original, because the factors below √a are obviously denser than those above. For large a, √a is much less than a/2. Commented May 16, 2017 at 16:55