Prime Factoriziation Algorithm
The Prime Factorization Algorithm is a mathematical procedure used to find the prime factors of a given number. Prime factors are the prime numbers that can be multiplied together to produce the original number. The algorithm involves dividing the number by successive prime numbers, starting from the smallest prime (which is 2), and continuing until the quotient is a prime number. The main goal of this algorithm is to break down a composite number into its simplest building blocks, which are its prime factors. This allows for a better understanding of the number's properties, composition, and can also be useful in various mathematical and cryptographic applications.
In the process of prime factorization, we first check if the given number is divisible by 2, which is the smallest prime number. If it is divisible, we divide the number by 2 and continue this process until the quotient is not divisible by 2 anymore. Then, we move on to the next smallest prime number (which is 3) and perform the same steps. We continue this process of dividing by successive prime numbers until the quotient is a prime number itself, at which point the process is complete. The list of prime divisors obtained in this process represents the prime factorization of the original number. This algorithm can be implemented using various programming languages and techniques, and it is a fundamental concept in number theory and the study of prime numbers.
/*
AUTHOR: Christian Bender
DATE: 12.02.2019
DESCRIPTION: This program calculates the prime factoriziation of a positive integer > 1
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/* initial length of the dynamic array */
#define LEN 10
/* increasing range */
#define STEP 5
/*
this type is for the representation of the prim factoriziation
- its series/range of prime factors
- its length : numbers of prime factors
*/
typedef struct data
{
int * range;
int length;
} range;
typedef range* Range;
/* int_fac : calculates the prime factoriziation of positive integers */
Range int_fact(int);
/* print_arr : prints the integer (heap) array*/
void print_arr(Range);
/* increase : increases the dynamic integer array */
int * increase(int *, int);
/* destroy: destroys the range-structure */
void destroy(Range);
/*
main : simle frame program with a simple UI
*/
int main()
{
int n = 0; /* for user input */
printf("\t\tPrim factoriziation\n\n");
printf("positive integer (> 1) ? ");
scanf("%d", &n);
Range r = int_fact(n);
printf("\nThe factoriziation are: ");
print_arr(r);
destroy(r);
return 0;
}
Range int_fact(int n)
{
assert(n > 1); /* precondition : n must be greater then 1*/
int len = LEN;
int count = 0;
int i = 0;
int * range = (int *) malloc(sizeof(int) * len);
assert(range);
Range pstr = (Range) malloc(sizeof(range));
assert(pstr);
while (n % 2 == 0)
{
n /= 2;
if (i < len)
{
range[i] = 2;
i++;
}
else
{
range = increase(range, len);
len += STEP;
range[i] = 2;
i++;
}
count++;
}
int j = 3;
while (j*j <= n)
{
while (n % j == 0)
{
n /= j;
if (i < len)
{
range[i] = j;
i++;
}
else
{
range = increase(range, len);
len += STEP;
range[i] = j;
i++;
}
count++;
}
j += 2;
}
if (n > 1)
{
if (i < len)
{
range[i] = n;
i++;
}
else
{
range = increase(range, len);
len += STEP;
range[i] = n;
i++;
}
count++;
}
pstr->range = range;
pstr->length = count;
return pstr;
}
void print_arr(Range pStr)
{
assert(pStr); /* checks whether pStr is a null-pointer */
int i = 0;
printf("\n");
for (i; i < pStr->length; i++)
{
if (i == 0)
printf("%d", pStr->range[0]);
else
printf("-%d", pStr->range[i]);
}
printf("\n");
}
int * increase(int * arr, int len)
{
assert(arr); /* checks whether arr is a null-pointer */
int * tmp = (int*) realloc(arr, sizeof(int) * (len + STEP));
assert(tmp);
return tmp;
// assert(arr);
}
void destroy(Range r)
{
free(r->range);
free(r);
}
