i have a code and im trying to get a O(sqrt(n)) without using math library in c

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int is_abundant(int num);
int main()
{
    int num;
    scanf("%d", &num);
    printf("%d\n", is_abundant(num));
    return 0;
}
int is_abundant(int num)
{
    int sum = 1;
    for (int i = 1; i < num; i  ) {
        if (num % i == 0)
        {
            sum  = i;
        }
    }
    sum = sum - num;
    if (sum > num) 
    {
        return 1;
    }
    else
        return 0;
}

what can i do to get O(sqrt(n)) ? any help ?

CodePudding user response：

When num % i == 0 is true, num % (num / i) == 0 will also be true.

Therefore, you can reduce the loop

    for (int i = 1; i < num; i  ) {
        if (num % i == 0)
        {
            sum  = i;
        }
    }

to

    if (num > 1) {
        for (int i = 1; i * i <= num; i  ) {
            if (num % i == 0)
            {
                sum  = i;
                if (num / i > i) sum  = num / i;
            }
        }
    }

Note that simply changing the condition i < num to i * i <= num will allow it to enter the loop when num = 1, so I added an if statement to deal with this case.

CodePudding user response：

For finding out factors you don't have to run the loop till n times, rather you can just run it till i <= sqrt(n) times or if you don't want to use sqrt lib then simply multiply i two times check if it is less than or equal to num or not.

int is_abundant(int num)
{
    int sum = 1;
    for (int i = 1; i*i <= num; i  ) {
        if (num % i == 0)
        {
            sum  = i;
        }
    }
    sum = sum - num;
    if (sum > num) 
    {
        return 1;
    }
    else
        return 0;
}