# Sokrates on Oracle

## The Fundamental theorem of arithmetic – SQL version

Posted by Matthias Rogel on 26. May 2015

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes, see for example Wolfram MathWorld or Wikipedia.

Here is the SQL-Version, we compute this for all integers up to 100

```with bound as
(
select 100 as bound from dual
),
n_until_bound as (
select level+1 n
from dual
connect by level <= (select bound.bound from bound)
),
primes_under_bound as
(
select n_until_bound.n as prime
from n_until_bound
minus
select n1.n * n2.n
from n_until_bound n1, n_until_bound n2
where n1.n <= n2.n
and n1.n <= (select sqrt(bound.bound) from bound)
),
primepowers_until_bound as
(
select p.prime, l.exponent
from primes_under_bound p, lateral(select level as exponent from dual connect by level <= log(p.prime, (select bound.bound from bound))) l
),
factors as
(
select n.n, pb.prime, pb.exponent
from n_until_bound n, primepowers_until_bound pb
where mod(n.n, power(pb.prime, pb.exponent)) = 0
),
largestfactors as
(
select
f.n, f.prime, min(f.exponent) keep(dense_rank first order by f.exponent desc) as exponent
from factors f
group by f.n, f.prime
)
select /*+pallel */ lf.n || ' = ' || listagg(lf.prime || case when lf.exponent > 1 then ' ^ ' || lf.exponent end, ' * ') within group(order by lf.prime asc) as factorization
from largestfactors lf
group by lf.n
order by lf.n
FACTORIZATION
----------------------------------------------------------------------------------------------------
2 = 2
3 = 3
4 = 2 ^ 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 ^ 3
9 = 3 ^ 2
10 = 2 * 5
11 = 11
12 = 2 ^ 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 ^ 4
17 = 17
18 = 2 * 3 ^ 2
19 = 19
20 = 2 ^ 2 * 5
21 = 3 * 7
22 = 2 * 11
23 = 23
24 = 2 ^ 3 * 3
25 = 5 ^ 2
26 = 2 * 13
27 = 3 ^ 3
28 = 2 ^ 2 * 7
29 = 29
30 = 2 * 3 * 5
31 = 31
32 = 2 ^ 5
33 = 3 * 11
34 = 2 * 17
35 = 5 * 7
36 = 2 ^ 2 * 3 ^ 2
37 = 37
38 = 2 * 19
39 = 3 * 13
40 = 2 ^ 3 * 5
41 = 41
42 = 2 * 3 * 7
43 = 43
44 = 2 ^ 2 * 11
45 = 3 ^ 2 * 5
46 = 2 * 23
47 = 47
48 = 2 ^ 4 * 3
49 = 7 ^ 2
50 = 2 * 5 ^ 2
51 = 3 * 17
52 = 2 ^ 2 * 13
53 = 53
54 = 2 * 3 ^ 3
55 = 5 * 11
56 = 2 ^ 3 * 7
57 = 3 * 19
58 = 2 * 29
59 = 59
60 = 2 ^ 2 * 3 * 5
61 = 61
62 = 2 * 31
63 = 3 ^ 2 * 7
64 = 2 ^ 6
65 = 5 * 13
66 = 2 * 3 * 11
67 = 67
68 = 2 ^ 2 * 17
69 = 3 * 23
70 = 2 * 5 * 7
71 = 71
72 = 2 ^ 3 * 3 ^ 2
73 = 73
74 = 2 * 37
75 = 3 * 5 ^ 2
76 = 2 ^ 2 * 19
77 = 7 * 11
78 = 2 * 3 * 13
79 = 79
80 = 2 ^ 4 * 5
81 = 3 ^ 4
82 = 2 * 41
83 = 83
84 = 2 ^ 2 * 3 * 7
85 = 5 * 17
86 = 2 * 43
87 = 3 * 29
88 = 2 ^ 3 * 11
89 = 89
90 = 2 * 3 ^ 2 * 5
91 = 7 * 13
92 = 2 ^ 2 * 23
93 = 3 * 31
94 = 2 * 47
95 = 5 * 19
96 = 2 ^ 5 * 3
97 = 97
98 = 2 * 7 ^ 2
99 = 3 ^ 2 * 11
100 = 2 ^ 2 * 5 ^ 2

```

### One Response to “The Fundamental theorem of arithmetic – SQL version”

1. ### Matthias Rogelsaid

we also can verify the decomposition we found:

```with bound as
(
select 100 as bound from dual
),
n_until_bound as (
select level+1 n
from dual
connect by level <= (select bound.bound from bound)
),
primes_under_bound as
(
select n_until_bound.n as prime
from n_until_bound
minus
select n1.n * n2.n
from n_until_bound n1, n_until_bound n2
where n1.n <= n2.n
and n1.n <= (select sqrt(bound.bound) from bound)
),
primepowers_until_bound as
(
select p.prime, l.exponent
from primes_under_bound p, (select level as exponent from dual connect by level <= log(2, (select bound.bound from bound))) l
where power(p.prime, l.exponent) <= (select bound.bound from bound)
),
factors as
(
select n.n, pb.prime, pb.exponent
from n_until_bound n, primepowers_until_bound pb
where mod(n.n, power(pb.prime, pb.exponent)) = 0
),
largestfactors as
(
select
f.n, f.prime, min(f.exponent) keep(dense_rank first order by f.exponent desc) as exponent
from factors f
group by f.n, f.prime
),
asproduct as
(
select
lf.n, listagg(lf.prime, ' * ') within group(order by null) as product
from
largestfactors lf,
lateral(select level l from dual connect by level <= lf.exponent) exps
group by lf.n
)
select /*+parallel */
lf.n || ' = ' ||
listagg(case when lf.exponent > 1 then '(' || lf.prime || ' ^ ' || lf.exponent || ')' else '' || lf.prime end, ' * ')
within group(order by lf.prime asc)
as factorization,
(select 'X' from asproduct ap where ap.n = lf.n and lf.n = xmlquery(ap.product returning content).getNumberVal()) as verified
from largestfactors lf
group by lf.n
order by lf.n
/

FACTORIZATION                  VERIFIED
------------------------------ --------------------
2 = 2                          X
3 = 3                          X
4 = (2 ^ 2)                    X
5 = 5                          X
6 = 2 * 3                      X
7 = 7                          X
8 = (2 ^ 3)                    X
9 = (3 ^ 2)                    X
10 = 2 * 5                     X
11 = 11                        X
12 = (2 ^ 2) * 3               X
13 = 13                        X
14 = 2 * 7                     X
15 = 3 * 5                     X
16 = (2 ^ 4)                   X
17 = 17                        X
18 = 2 * (3 ^ 2)               X
19 = 19                        X
20 = (2 ^ 2) * 5               X
21 = 3 * 7                     X
22 = 2 * 11                    X
23 = 23                        X
24 = (2 ^ 3) * 3               X
25 = (5 ^ 2)                   X
26 = 2 * 13                    X
27 = (3 ^ 3)                   X
28 = (2 ^ 2) * 7               X
29 = 29                        X
30 = 2 * 3 * 5                 X
31 = 31                        X
32 = (2 ^ 5)                   X
33 = 3 * 11                    X
34 = 2 * 17                    X
35 = 5 * 7                     X
36 = (2 ^ 2) * (3 ^ 2)         X
37 = 37                        X
38 = 2 * 19                    X
39 = 3 * 13                    X
40 = (2 ^ 3) * 5               X
41 = 41                        X
42 = 2 * 3 * 7                 X
43 = 43                        X
44 = (2 ^ 2) * 11              X
45 = (3 ^ 2) * 5               X
46 = 2 * 23                    X
47 = 47                        X
48 = (2 ^ 4) * 3               X
49 = (7 ^ 2)                   X
50 = 2 * (5 ^ 2)               X
51 = 3 * 17                    X
52 = (2 ^ 2) * 13              X
53 = 53                        X
54 = 2 * (3 ^ 3)               X
55 = 5 * 11                    X
56 = (2 ^ 3) * 7               X
57 = 3 * 19                    X
58 = 2 * 29                    X
59 = 59                        X
60 = (2 ^ 2) * 3 * 5           X
61 = 61                        X
62 = 2 * 31                    X
63 = (3 ^ 2) * 7               X
64 = (2 ^ 6)                   X
65 = 5 * 13                    X
66 = 2 * 3 * 11                X
67 = 67                        X
68 = (2 ^ 2) * 17              X
69 = 3 * 23                    X
70 = 2 * 5 * 7                 X
71 = 71                        X
72 = (2 ^ 3) * (3 ^ 2)         X
73 = 73                        X
74 = 2 * 37                    X
75 = 3 * (5 ^ 2)               X
76 = (2 ^ 2) * 19              X
77 = 7 * 11                    X
78 = 2 * 3 * 13                X
79 = 79                        X
80 = (2 ^ 4) * 5               X
81 = (3 ^ 4)                   X
82 = 2 * 41                    X
83 = 83                        X
84 = (2 ^ 2) * 3 * 7           X
85 = 5 * 17                    X
86 = 2 * 43                    X
87 = 3 * 29                    X
88 = (2 ^ 3) * 11              X
89 = 89                        X
90 = 2 * (3 ^ 2) * 5           X
91 = 7 * 13                    X
92 = (2 ^ 2) * 23              X
93 = 3 * 31                    X
94 = 2 * 47                    X
95 = 5 * 19                    X
96 = (2 ^ 5) * 3               X
97 = 97                        X
98 = 2 * (7 ^ 2)               X
99 = (3 ^ 2) * 11              X
100 = (2 ^ 2) * (5 ^ 2)        X
```