Category talk:Go-rcu: Difference between revisions
Content added Content deleted
(→Source code: Added PrimeCount method.) |
m (Missing comma.) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
===Source code=== |
===Source code=== |
||
< |
<syntaxhighlight lang="go">package rcu |
||
import ( |
import ( |
||
"fmt" |
"fmt" |
||
"golang.org/x/exp/constraints" |
|||
" |
"math" |
||
) |
) |
||
type Int = constraints.Integer |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
if x > y { |
if x > y { |
||
return x |
return x |
||
Line 15: | Line 18: | ||
} |
} |
||
// Returns the smaller of two |
// Returns the smaller of two integers. |
||
func Min(x, y |
func Min[T Int](x, y T) T { |
||
if x < y { |
if x < y { |
||
return x |
return x |
||
Line 23: | Line 26: | ||
} |
} |
||
// Returns the absolute value of an |
// Returns the absolute value of an integer. |
||
func Abs(x |
func Abs[T Int](x T) T { |
||
if x < 0 { |
if x < 0 { |
||
return -x |
return -x |
||
Line 31: | Line 34: | ||
} |
} |
||
// Returns the greatest common divisor of two |
// Returns the greatest common divisor of two integers. |
||
func Gcd(x, y |
func Gcd[T Int](x, y T) T { |
||
for y != 0 { |
for y != 0 { |
||
x, y = y, x%y |
x, y = y, x%y |
||
Line 39: | Line 42: | ||
} |
} |
||
// Returns the least common multiple of two |
// Returns the least common multiple of two integers. |
||
func Lcm(x, y |
func Lcm[T Int](x, y T) T { return Abs(x*y) / Gcd(x, y) } |
||
// Returns whether or not an |
// Returns whether or not an integer is prime. |
||
func IsPrime(n |
func IsPrime[T Int](n T) bool { |
||
switch { |
switch { |
||
case n < 2: |
case n < 2: |
||
Line 51: | Line 54: | ||
case n%3 == 0: |
case n%3 == 0: |
||
return n == 3 |
return n == 3 |
||
case n%5 == 0: |
|||
⚫ | |||
default: |
default: |
||
d := |
d := T(7) |
||
wheel := []T{4, 2, 4, 2, 4, 6, 2, 6} |
|||
for { |
|||
for _, w := range wheel { |
|||
if d*d > n { |
|||
return true |
|||
} |
|||
if n%d == 0 { |
|||
return false |
|||
} |
|||
d += w |
|||
} |
} |
||
⚫ | |||
} |
} |
||
return true |
return true |
||
Line 71: | Line 78: | ||
// c[i] is false if 'i' is prime or true if 'i' is composite. |
// c[i] is false if 'i' is prime or true if 'i' is composite. |
||
// Optionally processes even numbers >= 4. |
// Optionally processes even numbers >= 4. |
||
func PrimeSieve(limit |
func PrimeSieve[T Int](limit T, processEven bool) []bool { |
||
limit++ |
limit++ |
||
// True denotes composite, false denotes prime. |
// True denotes composite, false denotes prime. |
||
Line 78: | Line 85: | ||
c[1] = true |
c[1] = true |
||
if processEven { |
if processEven { |
||
for i := 4; i < limit; i += 2 { |
for i := T(4); i < limit; i += 2 { |
||
c[i] = true |
c[i] = true |
||
} |
} |
||
} |
} |
||
p := 3 // Start from 3. |
p := T(3) // Start from 3. |
||
for { |
for { |
||
p2 := p * p |
p2 := p * p |
||
Line 102: | Line 109: | ||
// Returns a slice of all primes up to and including 'limit'. |
// Returns a slice of all primes up to and including 'limit'. |
||
func Primes(limit |
func Primes[T Int](limit T) []T { |
||
c := PrimeSieve(limit, false) |
c := PrimeSieve(limit, false) |
||
if limit < 2 { |
if limit < 2 { |
||
return [] |
return []T{} |
||
} |
} |
||
primes := [] |
primes := []T{2} |
||
for i := 3; i < len(c); i += 2 { |
for i := T(3); i < T(len(c)); i += 2 { |
||
if !c[i] { |
if !c[i] { |
||
primes = append(primes, i) |
primes = append(primes, i) |
||
Line 118: | Line 125: | ||
// Sieves for primes up to and including 'n' and returns how many there are. |
// Sieves for primes up to and including 'n' and returns how many there are. |
||
// Uses an algorithm better suited to counting than the one used in the PrimeSieve method. |
// Uses an algorithm better suited to counting than the one used in the PrimeSieve method. |
||
func PrimeCount(n |
func PrimeCount[T Int](n T) int { |
||
if n < 2 { |
if n < 2 { |
||
return 0 |
return 0 |
||
} |
|||
if n == 2 { |
|||
return 1 |
|||
} |
} |
||
count := 1 |
count := 1 |
||
k := (n-3)/2 + 1 |
k := (n-3)/2 + 1 |
||
marked := make([]bool, k) // all false by default |
marked := make([]bool, k) // all false by default |
||
limit := ( |
limit := (T(math.Sqrt(float64(n)))-3)/2 + 1 |
||
for i := 0; i < limit; i++ { |
for i := T(0); i < limit; i++ { |
||
if !marked[i] { |
if !marked[i] { |
||
p := 2*i + 3 |
p := 2*i + 3 |
||
Line 135: | Line 145: | ||
} |
} |
||
} |
} |
||
for i := 0; i < k; i++ { |
for i := T(0); i < k; i++ { |
||
if !marked[i] { |
if !marked[i] { |
||
count++ |
count++ |
||
Line 144: | Line 154: | ||
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5]. |
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5]. |
||
func PrimeFactors(n |
func PrimeFactors[T Int](n T) []T { |
||
if n < 2 { |
if n < 2 { |
||
return [] |
return []T{} |
||
} |
} |
||
inc := [] |
inc := []T{4, 2, 4, 2, 4, 6, 2, 6} |
||
var factors [] |
var factors []T |
||
for n%2 == 0 { |
for n%2 == 0 { |
||
factors = append(factors, 2) |
factors = append(factors, 2) |
||
Line 162: | Line 172: | ||
n = n / 5 |
n = n / 5 |
||
} |
} |
||
for k, i := 7, 0; k*k <= n; { |
for k, i := T(7), 0; k*k <= n; { |
||
if n%k == 0 { |
if n%k == 0 { |
||
factors = append(factors, k) |
factors = append(factors, k) |
||
Line 178: | Line 188: | ||
// Returns all the divisors of 'n' including 1 and 'n' itself. |
// Returns all the divisors of 'n' including 1 and 'n' itself. |
||
func Divisors(n |
func Divisors[T Int](n T) []T { |
||
if n < 1 { |
if n < 1 { |
||
return [] |
return []T{} |
||
} |
} |
||
var divisors [] |
var divisors []T |
||
var divisors2 [] |
var divisors2 []T |
||
i := 1 |
i := T(1) |
||
k := 1 |
k := T(1) |
||
if n%2 == 1 { |
if n%2 == 1 { |
||
k = 2 |
k = 2 |
||
Line 206: | Line 216: | ||
// Returns all the divisors of 'n' excluding 'n'. |
// Returns all the divisors of 'n' excluding 'n'. |
||
func ProperDivisors(n |
func ProperDivisors[T Int](n T) []T { |
||
d := Divisors(n) |
d := Divisors(n) |
||
c := len(d) |
c := len(d) |
||
if c <= 1 { |
if c <= 1 { |
||
return [] |
return []T{} |
||
} |
} |
||
return d[0 : len(d)-1] |
return d[0 : len(d)-1] |
||
} |
} |
||
// Reverses a slice of |
// Reverses a slice of integers in place. |
||
func ReverseInts(s [] |
func ReverseInts[T Int](s []T) { |
||
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { |
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { |
||
s[i], s[j] = s[j], s[i] |
s[i], s[j] = s[j], s[i] |
||
Line 222: | Line 232: | ||
} |
} |
||
// Returns a slice of an |
// Returns a slice of an integer's digits in base b. |
||
func Digits(n, b int) []int { |
func Digits[T Int](n T, b int) []int { |
||
if n == 0 { |
if n == 0 { |
||
return []int{0} |
return []int{0} |
||
Line 229: | Line 239: | ||
var digits []int |
var digits []int |
||
for n > 0 { |
for n > 0 { |
||
digits = append(digits, n%b) |
digits = append(digits, int(n%T(b))) |
||
n /= b |
n /= T(b) |
||
} |
} |
||
ReverseInts(digits) |
ReverseInts(digits) |
||
Line 236: | Line 246: | ||
} |
} |
||
// Returns the sum of an |
// Returns the sum of an integer's digits in base b. |
||
func DigitSum(n, b int) int { |
func DigitSum[T Int](n T, b int) int { |
||
sum := 0 |
sum := 0 |
||
for n > 0 { |
for n > 0 { |
||
sum += n % b |
sum += int(n % T(b)) |
||
n /= b |
n /= T(b) |
||
} |
} |
||
return sum |
return sum |
||
} |
} |
||
// Returns the sum of a slice of |
// Returns the sum of a slice of integers. |
||
func SumInts(a [] |
func SumInts[T Int](a []T) T { |
||
sum := 0 |
sum := T(0) |
||
for _, i := range a { |
for _, i := range a { |
||
sum += i |
sum += i |
||
Line 255: | Line 265: | ||
} |
} |
||
// Returns the maximum of a slice of |
// Returns the maximum of a slice of integers. |
||
func MaxInts(a [] |
func MaxInts[T Int](a []T) T { |
||
max := |
max := a[0] |
||
for _, i := range a { |
for _, i := range a[1:] { |
||
if i > max { |
if i > max { |
||
max = i |
max = i |
||
Line 266: | Line 276: | ||
} |
} |
||
// Returns the minimum of a slice of |
// Returns the minimum of a slice of integers |
||
func MinInts(a [] |
func MinInts[T Int](a []T) T { |
||
min := |
min := a[0] |
||
for _, i := range a { |
for _, i := range a[1:] { |
||
if i < min { |
if i < min { |
||
min = i |
min = i |
||
Line 277: | Line 287: | ||
} |
} |
||
// Adds thousand separators to an |
// Adds thousand separators to an integer. |
||
func Commatize(n |
func Commatize[T Int](n T) string { |
||
s := fmt.Sprintf("%d", n) |
s := fmt.Sprintf("%d", n) |
||
if n < 0 { |
if n < 0 { |
||
Line 293: | Line 303: | ||
} |
} |
||
// Prints a slice of |
// Prints a slice of integers in tabular form with a given row and column size |
||
// and optionally comma separators. |
// and optionally comma separators. |
||
func PrintTable(s [] |
func PrintTable[T Int](s []T, rowSize, colSize int, commas bool) { |
||
for i := 0; i < len(s); i++ { |
for i := 0; i < len(s); i++ { |
||
if !commas { |
if !commas { |
||
Line 309: | Line 319: | ||
fmt.Println() |
fmt.Println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
Latest revision as of 22:35, 27 April 2023
Source code
package rcu
import (
"fmt"
"golang.org/x/exp/constraints"
"math"
)
type Int = constraints.Integer
// Returns the larger of two integers.
func Max[T Int](x, y T) T {
if x > y {
return x
}
return y
}
// Returns the smaller of two integers.
func Min[T Int](x, y T) T {
if x < y {
return x
}
return y
}
// Returns the absolute value of an integer.
func Abs[T Int](x T) T {
if x < 0 {
return -x
}
return x
}
// Returns the greatest common divisor of two integers.
func Gcd[T Int](x, y T) T {
for y != 0 {
x, y = y, x%y
}
return x
}
// Returns the least common multiple of two integers.
func Lcm[T Int](x, y T) T { return Abs(x*y) / Gcd(x, y) }
// Returns whether or not an integer is prime.
func IsPrime[T Int](n T) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
case n%5 == 0:
return n == 5
default:
d := T(7)
wheel := []T{4, 2, 4, 2, 4, 6, 2, 6}
for {
for _, w := range wheel {
if d*d > n {
return true
}
if n%d == 0 {
return false
}
d += w
}
}
return true
}
}
// Sieves for primes up to and including 'limit'.
// Returns a bool slice 'c' of size (limit + 1) where:
// c[i] is false if 'i' is prime or true if 'i' is composite.
// Optionally processes even numbers >= 4.
func PrimeSieve[T Int](limit T, processEven bool) []bool {
limit++
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
c[0] = true
c[1] = true
if processEven {
for i := T(4); i < limit; i += 2 {
c[i] = true
}
}
p := T(3) // Start from 3.
for {
p2 := p * p
if p2 >= limit {
break
}
for i := p2; i < limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
return c
}
// Returns a slice of all primes up to and including 'limit'.
func Primes[T Int](limit T) []T {
c := PrimeSieve(limit, false)
if limit < 2 {
return []T{}
}
primes := []T{2}
for i := T(3); i < T(len(c)); i += 2 {
if !c[i] {
primes = append(primes, i)
}
}
return primes
}
// Sieves for primes up to and including 'n' and returns how many there are.
// Uses an algorithm better suited to counting than the one used in the PrimeSieve method.
func PrimeCount[T Int](n T) int {
if n < 2 {
return 0
}
if n == 2 {
return 1
}
count := 1
k := (n-3)/2 + 1
marked := make([]bool, k) // all false by default
limit := (T(math.Sqrt(float64(n)))-3)/2 + 1
for i := T(0); i < limit; i++ {
if !marked[i] {
p := 2*i + 3
s := (p*p - 3) / 2
for j := s; j < k; j += p {
marked[j] = true
}
}
}
for i := T(0); i < k; i++ {
if !marked[i] {
count++
}
}
return count
}
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5].
func PrimeFactors[T Int](n T) []T {
if n < 2 {
return []T{}
}
inc := []T{4, 2, 4, 2, 4, 6, 2, 6}
var factors []T
for n%2 == 0 {
factors = append(factors, 2)
n = n / 2
}
for n%3 == 0 {
factors = append(factors, 3)
n = n / 3
}
for n%5 == 0 {
factors = append(factors, 5)
n = n / 5
}
for k, i := T(7), 0; k*k <= n; {
if n%k == 0 {
factors = append(factors, k)
n = n / k
} else {
k += inc[i]
i = (i + 1) % 8
}
}
if n > 1 {
factors = append(factors, n)
}
return factors
}
// Returns all the divisors of 'n' including 1 and 'n' itself.
func Divisors[T Int](n T) []T {
if n < 1 {
return []T{}
}
var divisors []T
var divisors2 []T
i := T(1)
k := T(1)
if n%2 == 1 {
k = 2
}
for ; i*i <= n; i += k {
if n%i == 0 {
divisors = append(divisors, i)
j := n / i
if j != i {
divisors2 = append(divisors2, j)
}
}
}
if len(divisors2) > 0 {
ReverseInts(divisors2)
divisors = append(divisors, divisors2...)
}
return divisors
}
// Returns all the divisors of 'n' excluding 'n'.
func ProperDivisors[T Int](n T) []T {
d := Divisors(n)
c := len(d)
if c <= 1 {
return []T{}
}
return d[0 : len(d)-1]
}
// Reverses a slice of integers in place.
func ReverseInts[T Int](s []T) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
// Returns a slice of an integer's digits in base b.
func Digits[T Int](n T, b int) []int {
if n == 0 {
return []int{0}
}
var digits []int
for n > 0 {
digits = append(digits, int(n%T(b)))
n /= T(b)
}
ReverseInts(digits)
return digits
}
// Returns the sum of an integer's digits in base b.
func DigitSum[T Int](n T, b int) int {
sum := 0
for n > 0 {
sum += int(n % T(b))
n /= T(b)
}
return sum
}
// Returns the sum of a slice of integers.
func SumInts[T Int](a []T) T {
sum := T(0)
for _, i := range a {
sum += i
}
return sum
}
// Returns the maximum of a slice of integers.
func MaxInts[T Int](a []T) T {
max := a[0]
for _, i := range a[1:] {
if i > max {
max = i
}
}
return max
}
// Returns the minimum of a slice of integers
func MinInts[T Int](a []T) T {
min := a[0]
for _, i := range a[1:] {
if i < min {
min = i
}
}
return min
}
// Adds thousand separators to an integer.
func Commatize[T Int](n T) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
// Prints a slice of integers in tabular form with a given row and column size
// and optionally comma separators.
func PrintTable[T Int](s []T, rowSize, colSize int, commas bool) {
for i := 0; i < len(s); i++ {
if !commas {
fmt.Printf("%*d ", colSize, s[i])
} else {
fmt.Printf("%*s ", colSize, Commatize(s[i]))
}
if (i+1)%rowSize == 0 {
fmt.Println()
}
}
if len(s)%rowSize != 0 {
fmt.Println()
}
}