Factorization

FINDING the factors of a NUMber N

Finding the prime factors is handled in the sub page C Programs/ Prime numbers, this page handles the problem of finding the factors of any number n.

For example: The factors of 28 is 1,2,4,7,14,28

As we can see that we if we find the factors 1,2,4 we know that the quotients from the divisors 1,2,4 is 28,14,7 is also the factors. My approach to this problem is similar with going through a loop and constantly changing the end of the loop.

Steps: Start a loop from 1 and check whether it divides our input number (of course it does). Now the divisor is added to list_1 and the quotient is added to list_2. The loop will now end at the quotient.

for example, starting with 28, first we have (1,28) then (2,14), (4,7) and so on.

The below program generates triangle numbers and find the divisor list over 500. The function int *return_divisors(int the_num,int *divisor_count); is the function of returns the address of the factors list and other functions are the supporting function.

for example: The factors of 76576500 (which is also a triangle number) is 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22, 25, 26, 28, 30, 33, 34, 35, 36, 39, 42, 44, 45, 50, 51, 52, 55, 60, 63, 65, 66, 68, 70, 75, 77, 78, 84, 85, 90, 91, 99, 100, 102, 105, 110, 117, 119, 125, 126, 130, 132, 140, 143, 150, 153, 154, 156, 165, 170, 175, 180, 182, 187, 195, 198, 204, 210, 220, 221, 225, 231, 234, 238, 250, 252, 255, 260, 273, 275, 286, 300, 306, 308, 315, 325, 330, 340, 350, 357, 364, 374, 375, 385, 390, 396, 420, 425, 429, 442, 450, 455, 462, 468, 476, 495, 500, 510, 525, 546, 550, 561, 572, 585, 595, 612, 630, 650, 660, 663, 693, 700, 714, 715, 748, 750, 765, 770, 780, 819, 825, 850, 858, 875, 884, 900, 910, 924, 935, 975, 990, 1001, 1020, 1050, 1071, 1092, 1100, 1105, 1122, 1125, 1155, 1170, 1190, 1260, 1275, 1287, 1300, 1309, 1326, 1365, 1375, 1386, 1428, 1430, 1500, 1530, 1540, 1547, 1575, 1625, 1638, 1650, 1683, 1700, 1716, 1750, 1785, 1820, 1870, 1925, 1950, 1980, 1989, 2002, 2100, 2125, 2142, 2145, 2210, 2244, 2250, 2275, 2310, 2340, 2380, 2431, 2475, 2550, 2574, 2618, 2625, 2652, 2730, 2750, 2772, 2805, 2860, 2925, 2975, 3003, 3060, 3094, 3150, 3250, 3276, 3300, 3315, 3366, 3465, 3500, 3570, 3575, 3740, 3825, 3850, 3900, 3927, 3978, 4004, 4095, 4125, 4250, 4284, 4290, 4420, 4500, 4550, 4620, 4641, 4675, 4862, 4875, 4950, 5005, 5100, 5148, 5236, 5250, 5355, 5460, 5500, 5525, 5610, 5775, 5850, 5950, 6006, 6188, 6300, 6375, 6435, 6500, 6545, 6630, 6732, 6825, 6930, 7140, 7150, 7293, 7650, 7700, 7735, 7854, 7875, 7956, 8190, 8250, 8415, 8500, 8580, 8925, 9009, 9100, 9282, 9350, 9625, 9724, 9750, 9900, 9945, 10010, 10500, 10710, 10725, 11050, 11220, 11375, 11550, 11700, 11781, 11900, 12012, 12155, 12375, 12750, 12870, 13090, 13260, 13650, 13860, 13923, 14025, 14300, 14586, 14625, 14875, 15015, 15300, 15470, 15708, 15750, 16380, 16500, 16575, 16830, 17017, 17325, 17850, 17875, 18018, 18564, 18700, 19125, 19250, 19500, 19635, 19890, 20020, 20475, 21420, 21450, 21879, 22100, 22750, 23100, 23205, 23375, 23562, 24310, 24750, 25025, 25500, 25740, 26180, 26775, 27300, 27625, 27846, 28050, 28875, 29172, 29250, 29750, 30030, 30940, 31500, 32175, 32725, 33150, 33660, 34034, 34125, 34650, 35700, 35750, 36036, 36465, 38250, 38500, 38675, 39270, 39780, 40950, 42075, 42900, 43758, 44625, 45045, 45500, 46410, 46750, 47124, 48620, 49500, 49725, 50050, 51051, 53550, 53625, 55250, 55692, 56100, 57750, 58500, 58905, 59500, 60060, 60775, 64350, 65450, 66300, 68068, 68250, 69300, 69615, 70125, 71500, 72930, 75075, 76500, 77350, 78540, 81900, 82875, 84150, 85085, 86625, 87516, 89250, 90090, 92820, 93500, 98175, 99450, 100100, 102102, 102375, 107100, 107250, 109395, 110500, 115500, 116025, 117810, 121550, 125125, 128700, 130900, 133875, 136500, 139230, 140250, 145860, 150150, 153153, 154700, 160875, 163625, 165750, 168300, 170170, 173250, 178500, 180180, 182325, 193375, 196350, 198900, 204204, 204750, 210375, 214500, 218790, 225225, 232050, 235620, 243100, 248625, 250250, 255255, 267750, 278460, 280500, 294525, 300300, 303875, 306306, 321750, 327250, 331500, 340340, 346500, 348075, 364650, 375375, 386750, 392700, 409500, 420750, 425425, 437580, 450450, 464100, 490875, 497250, 500500, 510510, 535500, 546975, 580125, 589050, 607750, 612612, 643500, 654500, 696150, 729300, 750750, 765765, 773500, 841500, 850850, 900900, 911625, 981750, 994500, 1021020, 1093950, 1126125, 1160250, 1178100, 1215500, 1276275, 1392300, 1472625, 1501500, 1531530, 1701700, 1740375, 1823250, 1963500, 2127125, 2187900, 2252250, 2320500, 2552550, 2734875, 2945250, 3063060, 3480750, 3646500, 3828825, 4254250, 4504500, 5105100, 5469750, 5890500, 6381375, 6961500, 7657650, 8508500, 10939500, 12762750, 15315300, 19144125, 25525500, 38288250, 76576500,

Divisors count = 576

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

/*The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors? */

// The answer is
// 76576500


int *return_divisors(int the_num,int *divisor_count);
bool IsDivisible(int *dividend, int *divisor,int *quotient);
void reverse_array(int *array_rev,int *array_size);
int *add_to_list(int *the_list,int the_value,int *list_count);

int main()
{
    // Generate triangle numbers
    int i,j,tri_n=0;

    for(i=1;i<20000;i++)
    {

        int div_count;
        tri_n = tri_n + i;
        int *divisor_list = return_divisors(tri_n,&div_count);

        if(div_count>=500)
        {
            printf("%d divisors are ",tri_n);
            for(j=0;j<div_count;j++)
            {
                printf("%d, ",*(divisor_list+j));
            }
            printf("\n Divisor count = %d\n",div_count);
            break;
        }
    }


    return 0;
}

int *return_divisors(int the_num,int *divisor_count)
{
    int *divisor_list_l,*divisor_list_u; // 1 list is to store divisors and the other is for quotient
    int divisor_size_l =0,divisor_size_u =0;// 1 var is to store divisors count and the other is for quotient count


    int i,k = 2; // k = 2 to start the loop

    for(i=1;i<k;i++)
    {
        if(IsDivisible(&the_num,&i,&k)==true)
        {
            if(i!=k) // To prevent square numbers divisors adding twice, example: 36 = 6*6
            {
                divisor_list_l=add_to_list(divisor_list_l,i,&divisor_size_l);// add the divisor to divisor_list_l <stores divisor>
                divisor_list_u=add_to_list(divisor_list_u,k,&divisor_size_u);// add the divisor to divisor_list_u <stores quotient>
            }
            else
            {
                divisor_list_l=add_to_list(divisor_list_l,i,&divisor_size_l);// add the divisor to divisor_list_l <stores divisor>
            }
        }
    }
    *(divisor_count) = 0; // Set the number of divisor count = 0
    reverse_array(divisor_list_u,&divisor_size_u); // Reverse the list of quotient

    int *return_list = malloc((divisor_size_l+divisor_size_u)*sizeof(int));
    memcpy(return_list,divisor_list_l,divisor_size_l*sizeof(int)); //Copy the memory of divisor list to our return list
    memcpy(return_list+divisor_size_l,divisor_list_u,divisor_size_u*sizeof(int));//Copy the memory of quotient list to our return list

    (*divisor_count) =divisor_size_l+divisor_size_u;
    return return_list;
}

bool IsDivisible(int *dividend, int *divisor, int *quotient)
{
    int remainder =(*dividend)- (int)((*(dividend)/(*(divisor)))*(*divisor));
    (*quotient) = (*dividend)/(*divisor);
    if(remainder == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void reverse_array(int *array_rev,int *array_size)
{
    int i,n = (*array_size)-1,temp;
    for(i=0;i<((*array_size)/2);i++)
    {
        temp = *(array_rev+i);
        *(array_rev+i)=(*(array_rev+n));
        *(array_rev+n) = temp;
        n--;
    }
}

int *add_to_list(int *the_list,int the_value,int *list_count)
{
    if((*list_count)==0)// There is no item in the list
    {
        the_list = (int *)malloc(1*sizeof(int)); // We initialize 1 space to the list
    }
    else
    {
        int *temp = (int *)realloc(the_list,(*(list_count)+1)*sizeof(int)); // Allocate one extra space
        if(temp != NULL)
        {
            the_list = temp;
        }
        else
        {
            printf("Error Allocating Memory");
        }
    }

    *(the_list+(*(list_count))) = the_value; // Adding the value here
    *(list_count) =(*(list_count))+1; // Increment the list count after addition
    return the_list; // return the list address
}