179 lines
3.0 KiB
V
179 lines
3.0 KiB
V
module euler
|
|
import math
|
|
|
|
pub fn range(start int, end int) []int {
|
|
mut result := []int
|
|
for i := start; i <= end; i++ {
|
|
result << i
|
|
}
|
|
return result
|
|
}
|
|
|
|
pub fn add(i int, j int) int { return i + j }
|
|
|
|
pub fn even(n int) bool {
|
|
return n % 2 == 0
|
|
}
|
|
|
|
pub fn prime(n u64) bool {
|
|
for i := u64(2); i <= u64(math.sqrt(f64(n))); i++ {
|
|
if n % i == 0 {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
pub fn factors(n u64) []u64 {
|
|
mut factors := []u64
|
|
for i := u64(2); i <= u64(math.sqrt(f64(n))); i++ {
|
|
if n % i == 0 && prime(i) {
|
|
factors << i
|
|
}
|
|
}
|
|
return factors
|
|
}
|
|
|
|
pub fn max(ints []u64) u64 {
|
|
mut max := u64(0)
|
|
for n in ints {
|
|
if n > max {
|
|
max = n
|
|
}
|
|
}
|
|
return max
|
|
}
|
|
|
|
pub fn two_combinations(ints []int) [][]int {
|
|
mut result := [[]int]
|
|
result = []
|
|
for i := 0; i < ints.len; i++ {
|
|
for j := i + 1; j < ints.len; j++ {
|
|
result << [[ints[i], ints[j]]]
|
|
}
|
|
}
|
|
return result
|
|
}
|
|
|
|
pub fn palindrome(n int) bool {
|
|
str := n.str()
|
|
for i := 0; i < str.len; i++ {
|
|
if str[i] != str[str.len-1-i] {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
fn check(n int, p int) []int {
|
|
mut result := []int
|
|
mut q := n / p
|
|
mut r := n % p
|
|
mut m := n
|
|
for r == 0 {
|
|
result << p
|
|
m = q
|
|
q = m / p
|
|
r = m % p
|
|
}
|
|
return result
|
|
}
|
|
|
|
fn trial_division(n int) []int {
|
|
mut factors := []int
|
|
factors << check(n, 2)
|
|
factors << check(n, 3)
|
|
mut p := 5
|
|
for p * p <= n {
|
|
factors << check(n, p)
|
|
p += 2
|
|
factors << check(n, p)
|
|
p += 4
|
|
}
|
|
if factors.len == 0 { factors << n }
|
|
return factors
|
|
}
|
|
|
|
pub fn prime_factorization(n int) map[string]int {
|
|
mut result := map[string]int
|
|
factors := trial_division(n)
|
|
for f in factors {
|
|
result[f.str()] = 0
|
|
mut num := n
|
|
for num % f == 0 {
|
|
result[f.str()] = result[f.str()] + 1
|
|
num /= f
|
|
}
|
|
}
|
|
return result
|
|
}
|
|
|
|
pub fn eratosthenes_sieve(n int) []bool {
|
|
mut sieve := [true].repeat(n + 1)
|
|
sieve[0] = false
|
|
sieve[1] = false
|
|
|
|
for i := 2; i <= int(math.sqrt(n)); i++ {
|
|
if (sieve[i]) {
|
|
for j := i * i; j <= n; j += i {
|
|
sieve[j] = false
|
|
}
|
|
}
|
|
}
|
|
|
|
return sieve
|
|
}
|
|
|
|
pub fn eratosthenes_sieve_expand(n int, sieve []bool) []bool
|
|
{
|
|
mut new_sieve := sieve
|
|
for i := sieve.len + 1; i <= n + 1; i++ {
|
|
new_sieve << true
|
|
}
|
|
|
|
for i := 2; i <= int(math.sqrt(n)); i++ {
|
|
if (new_sieve[i]) {
|
|
mut start := i * i
|
|
if (i * i >= sieve.len) {
|
|
start = sieve.len + i - (sieve.len % i)
|
|
}
|
|
for j := start; j <= n; j += i {
|
|
new_sieve[j] = false
|
|
}
|
|
}
|
|
}
|
|
|
|
return new_sieve
|
|
}
|
|
|
|
pub fn primes_up_to(n int) []int {
|
|
return primes_from_sieve(eratosthenes_sieve(n))
|
|
}
|
|
|
|
fn count_primes_from_sieve(sieve []bool) int {
|
|
mut result := 0
|
|
for b in sieve { if b { result++ } }
|
|
return result
|
|
}
|
|
|
|
fn primes_from_sieve(sieve []bool) []int {
|
|
mut result := []int
|
|
for index, b in sieve {
|
|
if b { result << index }
|
|
}
|
|
return result
|
|
}
|
|
|
|
pub fn find_nth_prime(n int) int {
|
|
mut sieve_size := 16
|
|
mut sieve := eratosthenes_sieve(sieve_size)
|
|
|
|
for count_primes_from_sieve(sieve) < n {
|
|
sieve_size *= 2
|
|
sieve = eratosthenes_sieve_expand(sieve_size, sieve)
|
|
}
|
|
|
|
primes := primes_from_sieve(sieve)
|
|
return primes[n - 1]
|
|
}
|