Skip to content

Instantly share code, notes, and snippets.

@Masa-Shin
Last active December 19, 2022 09:38
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Masa-Shin/085c2d8957045db3b1a31663defd7bdf to your computer and use it in GitHub Desktop.
Prime factaorization with TypeScript type system.
/* eslint-disable @typescript-eslint/no-unused-vars */
type NumToTuple<N extends number, Result extends unknown[] = []> = Result['length'] extends N
? Result
: NumToTuple<N, [unknown, ...Result]>
type Subtraction<N extends number, M extends number> = NumToTuple<N> extends [
...NumToTuple<M>,
...infer U
]
? U['length']
: never
const subtraction1: Subtraction<7, 4> = 3
const subtraction2: Subtraction<4, 4> = 0
// @ts-expect-error
const subtraction3: Subtraction<4, 7> = 0
type IsStrictlySmaller<
N extends number,
M extends number
> = Subtraction<N, M> extends never ? true : false
type IsDivisible<N extends number, M extends number> = 0 extends N
? true
: IsStrictlySmaller<N, M> extends true
? false
: IsDivisible<Subtraction<N, M>, M>
const isDivisible1: IsDivisible<3, 3> = true
const isDivisible2: IsDivisible<6, 3> = true
const isDivisible3: IsDivisible<5, 3> = false
// 割り算
type Division<N extends number, M extends number, Q extends unknown[] = []> = IsStrictlySmaller<N, M> extends true
? Q['length']
: Division<Subtraction<N, M>, M, [unknown, ...Q]>
const division1: Division<2, 3> = 0
const division2: Division<3, 2> = 1
const division3: Division<3, 3> = 1
const division4: Division<8, 3> = 2
const division5: Division<16, 4> = 4
// 余り付き割り算
type DivisionWithReminder<
N extends number,
M extends number,
Q extends unknown[] = [],
> = IsStrictlySmaller<N, M> extends true
? {
quotient: Q['length'],
reminder: N
}
: DivisionWithReminder<Subtraction<N, M>, M, [0, ...Q]>
// 素因数分解
type PrimeFactorList<N extends number, Divisor extends unknown[] = [unknown, unknown], Result extends number[] = []> = N extends 1
? Result
: Divisor['length'] extends N
? [...Result, N]
: IsDivisible<N, Divisor['length']> extends true
? PrimeFactorList<Division<N, Divisor['length']>, Divisor, [...Result, Divisor['length']]>
: PrimeFactorList<N, [0, ...Divisor], Result>
const pf1: PrimeFactorList<1> = []
const pf2: PrimeFactorList<2> = [2]
const pf3: PrimeFactorList<3> = [3]
const pf4: PrimeFactorList<4> = [2, 2]
const pf5: PrimeFactorList<5> = [5]
const pf6: PrimeFactorList<6> = [2, 3]
const pf7: PrimeFactorList<7> = [7]
const pf8: PrimeFactorList<8> = [2, 2, 2]
const pf9: PrimeFactorList<9> = [3, 3]
const pf10: PrimeFactorList<10> = [2, 5]
const pf11: PrimeFactorList<11> = [11]
const pf12: PrimeFactorList<12> = [2, 2, 3]
const pf13: PrimeFactorList<13> = [13]
const pf14: PrimeFactorList<14> = [2, 7]
const pf15: PrimeFactorList<15> = [3, 5]
const pf16: PrimeFactorList<16> = [2, 2, 2, 2]
const pf17: PrimeFactorList<17> = [17]
const pf18: PrimeFactorList<18> = [2, 3, 3]
const pf19: PrimeFactorList<19> = [19]
const pf20: PrimeFactorList<20> = [2, 2, 5]
const pf21: PrimeFactorList<21> = [3, 7]
const pf22: PrimeFactorList<22> = [2, 11]
const pf23: PrimeFactorList<23> = [23]
const pf24: PrimeFactorList<24> = [2, 2, 2, 3]
const pf25: PrimeFactorList<25> = [5, 5]
const pf26: PrimeFactorList<26> = [2, 13]
const pf27: PrimeFactorList<27> = [3, 3, 3]
const pf28: PrimeFactorList<28> = [2, 2, 7]
const pf29: PrimeFactorList<29> = [29]
const pf30: PrimeFactorList<30> = [2, 3, 5]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment