## 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

Advertisements

## Matthias Rogel said

we also can verify the decomposition we found: