# Prime Factorization

2018-09-08

This visualization is inspired by the works of Stephen Von Worley, which in turn is based on the original factorization diagrams idea by Brent Yorgey. Primes are visualized by a single unique pattern (circle) while non-primes are visualized by groups of prime patterns.

1

## Intuition for Viz

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime itself or a product of prime numbers.1

The fundamental theorem of arithemetic is the basis for this visualization. Given a number `n`, we are guaranteed an array of prime factors `[p1, p2, p3, ... pn]`, which we use for iteratively rendering subgroups of points in the visualization.

An implementation for `getPrimeFactors` could look like:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
``````/**
* Return array of prime factors (in ascending order) of n.
*
* Examples:
*  getPrimeFactors(1) // []
*  getPrimeFactors(10) // [5, 2]
*  getPrimeFactors(5) // 
*  getPrimeFactors(60) // [5, 3, 2, 2]
*  getPrimeFactors(120) // [5, 3, 2, 2, 2]
*  getPrimeFactors(240) // [5, 3, 2, 2, 2, 2]
*/
const getPrimeFactors = memoize(n => {
const result = [];
while (n > 1) {
const factor = getPrimeFactor(n);
result.push(factor);
n /= factor;
}
return result.reverse();
});

/**
* Return smallest prime factor of n.
*/
const getPrimeFactor = memoize(n => {
if (n % 2 === 0) {
return 2;
}
for (let i = 3; i <= Math.floor(Math.sqrt(n)); i += 2) {
if (n % i === 0) {
return i;
}
}
return n;
});
``````

For example, `getPrimeFactors(120)` returns an array of prime factors `[5, 3, 2, 2, 2]`. If we set the number in the viz to be `120`, we notice that the outer patterns are nested inwards with an ordering of `5`, `3`, `4` and `2`. This is very similar to the prime factorization of `120` with the observation that we try to merge consequetive groups of `2` into of `4`, which leads to a more aesthetically pleasing distribution of points.

We can implement a simple method `mergePrimeFactors` that receives an array of prime factors and merges `2` into `4` whenever possible:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
``````/**
* Merge consequtive '2's into '4' to support better visualization of points
* Examples:
*  mergePrimeFactors([2, 2, 2, 2]) // [4, 4]
*  mergePrimeFactors([2, 4, 4, 2]) // [2, 4, 4, 2]
*  mergePrimeFactors([2, 2, 2, 4]) // [4, 2, 4]
*/
const mergePrimeFactors = primeFactors => {
return primeFactors.reduce((a, x) => {
const last = a.length - 1;
if (a[last] === 2 && x === 2) {
a[last] = 4;
return a;
}
return [...a, x];
}, []);
};
``````

Feel free to pause the viz and plug in some of the interesting numbers provided above to study their respective prime factorization diagrams, or browse through the `d3` source code for details of the implementation.