Category talk:Go-rcu: Difference between revisions

Content added Content deleted
(→‎Source code: Bug fix.)
(Improved IsPrime function and genericized the whole package.)
Line 4: Line 4:
import (
import (
"fmt"
"fmt"
"golang.org/x/exp/constraints"
"math"
"math"
)
)


type Int = constraints.Integer
⚫
// Returns the larger of two ints.

⚫
func Max(x, y int) int {
⚫
// Returns the larger of two integers.
⚫
func Max[T Int](x, y T) T {
if x > y {
if x > y {
return x
return x
Line 15: Line 18:
}
}


// Returns the smaller of two ints.
// Returns the smaller of two integers.
func Min(x, y int) int {
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 int.
// Returns the absolute value of an integer.
func Abs(x int) int {
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 ints.
// Returns the greatest common divisor of two integers.
func Gcd(x, y int) int {
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 ints.
// Returns the least common multiple of two integers.
func Lcm(x, y int) int { return Abs(x*y) / Gcd(x, y) }
func Lcm[T Int](x, y T) T { return Abs(x*y) / Gcd(x, y) }


// Returns whether or not an int is prime.
// Returns whether or not an integer is prime.
func IsPrime(n int) bool {
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:
⚫
return n == 5
default:
default:
d := 5
d := T(7)
for d*d <= n {
wheel := []T{4, 2, 4, 2, 4, 6, 26}
if n%d == 0 {
for {
return false
for _, w := range wheel {
}
if d*d > n {
d += 2
return true
if n%d == 0 {
}
return false
if n%d == 0 {
return false
}
d += w
}
}
⚫
d += 4
}
}
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 int, processEven bool) []bool {
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 int) []int {
func Primes[T Int](limit T) []T {
c := PrimeSieve(limit, false)
c := PrimeSieve(limit, false)
if limit < 2 {
if limit < 2 {
return []int{}
return []T{}
}
}
primes := []int{2}
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 int) int {
func PrimeCount[T Int](n T) int {
if n < 2 {
if n < 2 {
return 0
return 0
Line 128: Line 135:
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 := (int(math.Sqrt(float64(n)))-3)/2 + 1
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 138: Line 145:
}
}
}
}
for i := 0; i < k; i++ {
for i := T(0); i < k; i++ {
if !marked[i] {
if !marked[i] {
count++
count++
Line 147: 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 int) []int {
func PrimeFactors[T Int](n T) []T {
if n < 2 {
if n < 2 {
return []int{}
return []T{}
}
}
inc := []int{4, 2, 4, 2, 4, 6, 2, 6}
inc := []T{4, 2, 4, 2, 4, 6, 2, 6}
var factors []int
var factors []T
for n%2 == 0 {
for n%2 == 0 {
factors = append(factors, 2)
factors = append(factors, 2)
Line 165: 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 181: 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 int) []int {
func Divisors[T Int](n T) []T {
if n < 1 {
if n < 1 {
return []int{}
return []T{}
}
}
var divisors []int
var divisors []T
var divisors2 []int
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 209: Line 216:


// Returns all the divisors of 'n' excluding 'n'.
// Returns all the divisors of 'n' excluding 'n'.
func ProperDivisors(n int) []int {
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 []int{}
return []T{}
}
}
return d[0 : len(d)-1]
return d[0 : len(d)-1]
}
}


// Reverses a slice of ints in place.
// Reverses a slice of integers in place.
func ReverseInts(s []int) {
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 225: Line 232:
}
}


// Returns a slice of an int's digits in base b.
// 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 232: 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 239: Line 246:
}
}


// Returns the sum of an int's digits in base b.
// 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 ints.
// Returns the sum of a slice of integers.
func SumInts(a []int) int {
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 258: Line 265:
}
}


// Returns the maximum of a slice of ints (64-bit assumed)
// Returns the maximum of a slice of integers.
func MaxInts(a []int) int {
func MaxInts[T Int](a []T) T {
max := -1 << 63
max := a[0]
for _, i := range a {
for _, i := range a[1:] {
if i > max {
if i > max {
max = i
max = i
Line 269: Line 276:
}
}


// Returns the minimum of a slice of ints (64-bit assumed)
// Returns the minimum of a slice of integers
func MinInts(a []int) int {
func MinInts[T Int](a []T) T {
min := 1<<63 - 1
min := a[0]
for _, i := range a {
for _, i := range a[1:] {
if i < min {
if i < min {
min = i
min = i
Line 280: Line 287:
}
}


// Adds thousand separators to an int.
// Adds thousand separators to an integer.
func Commatize(n int) string {
func Commatize[T Int](n T) string {
s := fmt.Sprintf("%d", n)
s := fmt.Sprintf("%d", n)
if n < 0 {
if n < 0 {
Line 296: Line 303:
}
}


// Prints a slice of ints in tabular form with a given row and column size
// 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 []int, rowSize, colSize int, commas bool) {
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 {
Retrieved from "https://rosettacode.org/wiki/Category_talk:Go-rcu"