How to resolve the algorithm Factors of an integer step by step in the C programming language
How to resolve the algorithm Factors of an integer step by step in the C programming language
Table of Contents
Problem Statement
Compute the factors of a positive integer. These factors are the positive integers by which the number being factored can be divided to yield a positive integer result. (Though the concepts function correctly for zero and negative integers, the set of factors of zero has countably infinite members, and the factors of negative integers can be obtained from the factors of related positive numbers without difficulty; this task does not require handling of either of these cases). Note that every prime number has two factors: 1 and itself.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Factors of an integer step by step in the C programming language
==> Notes for the first code...
-
The provided code defines functions for factorizing integers using the trial division algorithm, where factors are stored in a dynamically allocated list.
-
It includes a
typedef
structure namedFactors
that contains an integer array (int *list
) and a count of the factors (short count
). -
The
xferFactors
function takes aFactors
pointer, an integer array, and the size of that array, and transfers the factors from the array to theFactors
structure'slist
, reallocating it if necessary. -
The
factor
function takes an integer and aFactors
pointer as arguments. It calculates the factors of the input integer using a loop, stores them in a temporary array, and transfers them to theFactors
structure usingxferFactors
. -
In the
main
function, an array of integers to factorize is provided. AFactors
structure is initialized and passed tofactor
for each number, and the resulting factors are printed.
==> Notes for the second code...
-
The provided code defines functions for factorizing 32-bit unsigned integers using the trial division algorithm and stores the factors in a sorted list.
-
It uses the Sieve of Eratosthenes to precalculate a list of prime numbers up to 65536 (2^16) and stores them in the
primes
array. -
The
get_prime_factors
function takes an unsigned long integer and an array ofprime_factor
structures as input. It finds the prime factors of the input number and stores them in the array. -
The
get_factors
function takes an unsigned long integer and an array of unsigned long integers as input. It calculates the factors of the input number using the prime factors obtained fromget_prime_factors
. -
In the
main
function, several unsigned long integers are provided for factorization. The factors are calculated and printed in sorted order.
Source code in the c programming language
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *list;
short count;
} Factors;
void xferFactors( Factors *fctrs, int *flist, int flix )
{
int ix, ij;
int newSize = fctrs->count + flix;
if (newSize > flix) {
fctrs->list = realloc( fctrs->list, newSize * sizeof(int));
}
else {
fctrs->list = malloc( newSize * sizeof(int));
}
for (ij=0,ix=fctrs->count; ix<newSize; ij++,ix++) {
fctrs->list[ix] = flist[ij];
}
fctrs->count = newSize;
}
Factors *factor( int num, Factors *fctrs)
{
int flist[301], flix;
int dvsr;
flix = 0;
fctrs->count = 0;
free(fctrs->list);
fctrs->list = NULL;
for (dvsr=1; dvsr*dvsr < num; dvsr++) {
if (num % dvsr != 0) continue;
if ( flix == 300) {
xferFactors( fctrs, flist, flix );
flix = 0;
}
flist[flix++] = dvsr;
flist[flix++] = num/dvsr;
}
if (dvsr*dvsr == num)
flist[flix++] = dvsr;
if (flix > 0)
xferFactors( fctrs, flist, flix );
return fctrs;
}
int main(int argc, char*argv[])
{
int nums2factor[] = { 2059, 223092870, 3135, 45 };
Factors ftors = { NULL, 0};
char sep;
int i,j;
for (i=0; i<4; i++) {
factor( nums2factor[i], &ftors );
printf("\nfactors of %d are:\n ", nums2factor[i]);
sep = ' ';
for (j=0; j<ftors.count; j++) {
printf("%c %d", sep, ftors.list[j]);
sep = ',';
}
printf("\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 65536 = 2^16, so we can factor all 32 bit ints */
char bits[65536];
typedef unsigned long ulong;
ulong primes[7000], n_primes;
typedef struct { ulong p, e; } prime_factor; /* prime, exponent */
void sieve()
{
int i, j;
memset(bits, 1, 65536);
bits[0] = bits[1] = 0;
for (i = 0; i < 256; i++)
if (bits[i])
for (j = i * i; j < 65536; j += i)
bits[j] = 0;
/* collect primes into a list. slightly faster this way if dealing with large numbers */
for (i = j = 0; i < 65536; i++)
if (bits[i]) primes[j++] = i;
n_primes = j;
}
int get_prime_factors(ulong n, prime_factor *lst)
{
ulong i, e, p;
int len = 0;
for (i = 0; i < n_primes; i++) {
p = primes[i];
if (p * p > n) break;
for (e = 0; !(n % p); n /= p, e++);
if (e) {
lst[len].p = p;
lst[len++].e = e;
}
}
return n == 1 ? len : (lst[len].p = n, lst[len].e = 1, ++len);
}
int ulong_cmp(const void *a, const void *b)
{
return *(const ulong*)a < *(const ulong*)b ? -1 : *(const ulong*)a > *(const ulong*)b;
}
int get_factors(ulong n, ulong *lst)
{
int n_f, len, len2, i, j, k, p;
prime_factor f[100];
n_f = get_prime_factors(n, f);
len2 = len = lst[0] = 1;
/* L = (1); L = (L, L * p**(1 .. e)) forall((p, e)) */
for (i = 0; i < n_f; i++, len2 = len)
for (j = 0, p = f[i].p; j < f[i].e; j++, p *= f[i].p)
for (k = 0; k < len2; k++)
lst[len++] = lst[k] * p;
qsort(lst, len, sizeof(ulong), ulong_cmp);
return len;
}
int main()
{
ulong fac[10000];
int len, i, j;
ulong nums[] = {3, 120, 1024, 2UL*2*2*2*3*3*3*5*5*7*11*13*17*19 };
sieve();
for (i = 0; i < 4; i++) {
len = get_factors(nums[i], fac);
printf("%lu:", nums[i]);
for (j = 0; j < len; j++)
printf(" %lu", fac[j]);
printf("\n");
}
return 0;
}
You may also check:How to resolve the algorithm Numerical integration/Gauss-Legendre Quadrature step by step in the jq programming language
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the Processing programming language
You may also check:How to resolve the algorithm Last Friday of each month step by step in the Emacs Lisp programming language
You may also check:How to resolve the algorithm Sorting algorithms/Bead sort step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Sparkline in unicode step by step in the OCaml programming language