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
Sokrates on Oracle 
Matthias Rogel said
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