3
\$\begingroup\$

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;
}
\$\endgroup\$
7
  • \$\begingroup\$ You can skip "1" since 1, after 2 you can skip all even numbers. \$\endgroup\$
    – pacmaninbw
    Commented May 16, 2017 at 14:18
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Graipher
    Commented May 16, 2017 at 14:22
  • \$\begingroup\$ 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! \$\endgroup\$ Commented May 16, 2017 at 16:39
  • \$\begingroup\$ A quick observation that's too small for an answer - please don't get the bad habit of ignoring the return value from scanf()! \$\endgroup\$ Commented May 16, 2017 at 16:42
  • \$\begingroup\$ What do you mean by the return value? @TobySpeight \$\endgroup\$
    – 54D
    Commented May 16, 2017 at 16:45

1 Answer 1

3
\$\begingroup\$

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.

So your code would become:

#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;
}
\$\endgroup\$
9
  • \$\begingroup\$ Is there any way to list the factors in ascending order? This definitely runs much quicker but it isn't listed in order. \$\endgroup\$
    – 54D
    Commented May 16, 2017 at 14:27
  • \$\begingroup\$ @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... \$\endgroup\$
    – Graipher
    Commented May 16, 2017 at 15:01
  • \$\begingroup\$ @54D Also, you never said they should be in order in your question :) \$\endgroup\$
    – Graipher
    Commented May 16, 2017 at 15:02
  • \$\begingroup\$ I realized, sorry about that ^^|| I'll mark this as accepted anyway, because it directly answers the question. \$\endgroup\$
    – 54D
    Commented May 16, 2017 at 16:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented May 16, 2017 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.