From be5c8d8faa26a1b14d3ad77e2448539ff62c5f32 Mon Sep 17 00:00:00 2001 From: sgf Date: Mon, 23 Jan 2023 19:34:51 +0300 Subject: [PATCH] chg(max-div): Properly calculate total number of divisors. --- max-dividers/max-div.cpp | 116 ++++++++++++++++-- max-dividers/max-div.go | 220 +++++++++++++++++++++++++++++++++-- max-dividers/max-div_test.go | 102 ++++++++++++++-- 3 files changed, 410 insertions(+), 28 deletions(-) diff --git a/max-dividers/max-div.cpp b/max-dividers/max-div.cpp index 18863c2..b0735e2 100644 --- a/max-dividers/max-div.cpp +++ b/max-dividers/max-div.cpp @@ -1,26 +1,87 @@ #include using namespace std; +// Если число n можно представить в виде произведения простых делителей, как +// +// n = a^x * b^y * c^z +// +// где a, b, c - простые числа, то +// +// функции CountPrimeDividersX считают просто общее количество простых +// делителей, те +// +// x + y + z +// +// функции CountDividersX считают общее количество (разных) делителей, те +// +// (x + 1) * (y + 1) * (z + 1) +// + // Рекурсия. -int CountDividers1(int n) { +// Просто количество простых делителей. +int CountPrimeDividers1(int n) { for (int i = 2; i <= n; i++) if (n%i == 0) - return 1 + CountDividers1(n/i); + return 1 + CountPrimeDividers1(n/i); return 0; } +// Общее количество делителей. +int CountDividers1(int n) { + for (int i = 2; i <= n; i++) + if (n%i == 0) { + int k = 0; + for (; n%i == 0; k++) + n /= i; + return (k + 1) * CountDividers1(n); + } + return 1; +} + +// Меньше итераций цикла. +int CountDividers11(int n) { + if (n%2 == 0) { + int k = 0; + for (; n%2 == 0; k++) + n /= 2; + return (k + 1) * CountDividers11(n); + } + + for (int i = 3; i <= n; i += 2) { + if (n%i == 0) { + int k = 0; + for (; n%i == 0; k++) + n /= i; + return (k + 1) * CountDividers11(n); + } + } + return 1; +} + // Хвостовая рекурсия. Стек вызова функций (теоретически) не будет // увеличиваться в сравнении с рекусривной версией (хотя это зависит от // компилятора). -int CountDividers2(int acc, int n) { +int CountPrimeDividers2(int acc, int n) { for (int i = 2; i <= n; i++) if (n%i == 0) - return CountDividers2(acc + 1, n/i); + return CountPrimeDividers2(acc + 1, n/i); + return acc; +} + +// Общее количество делителей. +int CountDividers2(int acc, int n) { + for (int i = 2; i <= n; i++) + if (n%i == 0) { + int k = 0; + for (; n%i == 0; k++) + n /= i; + return CountDividers2((k + 1) * acc, n); + } return acc; } // Без рекурсии. -int CountDividers3(int n) { +int CountPrimeDividers3(int n) { int m = n; int acc = 0; while (m >= 2) @@ -33,12 +94,46 @@ int CountDividers3(int n) { return acc; } +// Общее количество делителей. +int CountDividers3(int n) { + int m = n; + int acc = 1; + while (m >= 2) { + for (int i = 2; i <= m; i++) { + if (m%i == 0) { + int k = 0; + for (; m%i == 0; k++) + m /= i; + acc *= (k + 1); + break; + } + } + } + return acc; +} + +int searchMaxPrimeDiv(int start, int end) { + int x = 0; + int m = 0; + for (int n = start; n <= end; n++) { + //int c = CountPrimeDividers1(n); + //int c = CountPrimeDividers2(0, n); + int c = CountPrimeDividers3(n); + if (c >= m) { + m = c; + x = n; + } + } + return x; +} + int searchMaxDiv(int start, int end) { int x = 0; int m = 0; for (int n = start; n <= end; n++) { //int c = CountDividers1(n); - //int c = CountDividers2(0, n); + //int c = CountDividers11(n); + //int c = CountDividers2(1, n); int c = CountDividers3(n); if (c >= m) { m = c; @@ -65,16 +160,21 @@ int origSearchMaxDiv(int start, int end) x = i; } } + cout << m << endl; return x; } int main() { int start = 394441; int end = 394505; + //int start = 2; + //int end = 36; int x; x = origSearchMaxDiv(start, end); - cout << x << endl; + cout << "origSearchMaxDiv: " << x << endl; x = searchMaxDiv(start, end); - cout << x << endl; + cout << "searchMaxDiv: " << x << endl; + x = searchMaxPrimeDiv(start, end); + cout << "searchMaxPrimeDiv: " << x << endl; } diff --git a/max-dividers/max-div.go b/max-dividers/max-div.go index 03fd394..6188328 100644 --- a/max-dividers/max-div.go +++ b/max-dividers/max-div.go @@ -10,29 +10,50 @@ const start_num = 1 //const end_num = 394505 const end_num = 10 -func CountDividers1(n int) int { +// If a number n can be represented as multiplication of prime factors like +// +// +// n = a^x * b^y * c^z +// +// where, a, b, c - prime numbers, then +// +// functions CountPrimeDividersX count the number of prime dividers, i.e. +// +// x + y + z +// +// functions CountDividersX count the total number of (different) dividers, +// i.e. +// +// (x + 1) * (y + 1) * (z + 1) +// + +// Recursive. +func CountPrimeDividers1(n int) int { fmt.Printf("Start with %v\n", n) for i := 2; i <= n; i++ { if n%i == 0 { fmt.Printf("found %v\n", i) - return 1 + CountDividers1(n/i) + return 1 + CountPrimeDividers1(n/i) } } return 0 } -func CountDividers2(acc, n int) int { +// Tail-recursive. +// 'acc' should start at 1. +func CountPrimeDividers2(acc, n int) int { //fmt.Printf("Start with %v (%v)\n", n, acc) for i := 2; i <= n; i++ { if n%i == 0 { //fmt.Printf("found %v\n", i) - return CountDividers2(acc + 1, n/i) + return CountPrimeDividers2(acc + 1, n/i) } } return acc } -func CountDividers3(n int) int { +// Cycle. +func CountPrimeDividers3(n int) int { m := n acc := 0 for m >= 2 { @@ -49,13 +70,187 @@ func CountDividers3(n int) int { return acc } +// Search the number in the range with maximum number of prime dividers. +func searchMaxPrimeDiv(start, end int) int { + var x, m int + for n := start; n <= end; n++ { + //fmt.Printf("n = %v\n", n) + //c := CountPrimeDividers1(n) + //c := CountPrimeDividers2(0, n) + c := CountPrimeDividers3(n) + //fmt.Printf(" %v has %v dividers\n", n, c) + if c >= m { + m = c + x = n + } + } + fmt.Println(x, m) + return x +} + + + +// Linear. +func CountDividers0(n int) int { + acc := 0 + for i := 1; i <= n; i++ { + if n%i == 0 { + acc++ + } + } + return acc +} + +// Recursive. +func CountDividers1(n int) int { + //fmt.Printf("Start with %v\n", n) + for i := 2; i <= n; i++ { + if n%i == 0 { + k := 0 + for ; n%i == 0; k++ { + n /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + return (k + 1) * CountDividers1(n) + } + } + return 1 +} + +// Optimised recursive. +func CountDividers11(n int) int { + //fmt.Printf("Start with %v\n", n) + if n%2 == 0 { + k := 0 + for ; n%2 == 0; k++ { + n /= 2 + } + //fmt.Printf("found 2 with power %v\n", k) + return (k + 1) * CountDividers11(n) + } + + for i := 3; i <= n; i += 2 { + if n%i == 0 { + k := 0 + for ; n%i == 0; k++ { + n /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + return (k + 1) * CountDividers11(n) + } + } + return 1 +} + +// Tail-recursive. +// 'acc' should start at 1. +func CountDividers2(acc, n int) int { + //fmt.Printf("Start with %v (%v)\n", n, acc) + for i := 2; i <= n; i++ { + if n%i == 0 { + k := 0 + for ; n%i == 0; k++ { + n /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + return CountDividers2((k + 1) * acc, n) + } + } + return acc +} + +// Optimised tail-recursive. +// 'acc' should start at 1. +func CountDividers22(acc, n int) int { + //fmt.Printf("Start with %v (%v)\n", n, acc) + if n%2 == 0 { + k := 0 + for ; n%2 == 0; k++ { + n /= 2 + } + //fmt.Printf("found 2 with power %v\n", k) + return CountDividers22((k + 1) * acc, n) + } + + for i := 3; i <= n; i += 2 { + if n%i == 0 { + k := 0 + for ; n%i == 0; k++ { + n /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + return CountDividers22((k + 1) * acc, n) + } + } + return acc +} + +// Cycle. +func CountDividers3(n int) int { + m := n + acc := 1 + for m >= 2 { + //fmt.Printf("Go with %v\n", m) + for i := 2; i <= m; i++ { + if m%i == 0 { + k := 0 + for ; m%i == 0; k++ { + m /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + acc *= (k + 1) + break + } + } + } + return acc +} + +// Optimised cycle. +func CountDividers33(n int) int { + m := n + acc := 1 + if m == 1 { + return 1 + } + if m%2 == 0 { + k := 0 + for ; m%2 == 0; k++ { + m /= 2 + } + //fmt.Printf("found 2 with power %v\n", k) + acc = k + 1 + } + + for m >= 3 { + //fmt.Printf("Go with %v\n", m) + for i := 3; i <= m; i += 2 { + if m%i == 0 { + k := 0 + for ; m%i == 0; k++ { + m /= i + } + //fmt.Printf("found %v with power %v\n", i, k) + acc *= (k + 1) + break + } + } + } + return acc +} + +// Search the number in the range with maximum number of (different) dividers. func searchMaxDiv(start, end int) int { var x, m int for n := start; n <= end; n++ { //fmt.Printf("n = %v\n", n) + //c := CountDividers0(n) //c := CountDividers1(n) - //c := CountDividers2(0, n) - c := CountDividers3(n) + c := CountDividers11(n) + //c := CountDividers2(1, n) + //c := CountDividers22(1, n) + //c := CountDividers3(n) + //c := CountDividers33(n) //fmt.Printf(" %v has %v dividers\n", n, c) if c >= m { m = c @@ -67,8 +262,15 @@ func searchMaxDiv(start, end int) int { } func main() { - r := CountDividers1(1541) + var r int + //r = CountDividers11(6) + //fmt.Println(r) + //r = CountDividers11(360) + //fmt.Println(r) + //r = CountDividers11(144) fmt.Println(r) - searchMaxDiv(2, 16) + searchMaxPrimeDiv(2, 36) + searchMaxDiv(2, 36) + searchMaxPrimeDiv(394441, 394505) searchMaxDiv(394441, 394505) } diff --git a/max-dividers/max-div_test.go b/max-dividers/max-div_test.go index 1bd0f59..f8e7f71 100644 --- a/max-dividers/max-div_test.go +++ b/max-dividers/max-div_test.go @@ -11,18 +11,30 @@ type tData struct { } var vals []tData = []tData{ - {2, 1}, - {3, 1}, - {4, 2}, - {8, 3}, - {10, 2}, - {11, 1}, - {18, 3}, - {32, 5}, - {34, 2}, - {121, 2}, + {1, 1}, + {2, 2}, + {3, 2}, + {4, 3}, + {8, 4}, + {10, 4}, + {11, 2}, + {18, 6}, + {32, 6}, + {34, 4}, + {121, 3}, + {144, 15}, + {360, 24}, } +func TestCountDividers0(t *testing.T) { + for _, v := range vals { + got := CountDividers0(v.val) + if got != v.res { + t.Errorf("CountDividers0 test fails at %v with %v instead of %v\n", v.val, got, v.res) + } + } +} + func TestCountDividers1(t *testing.T) { for _, v := range vals { got := CountDividers1(v.val) @@ -32,15 +44,33 @@ func TestCountDividers1(t *testing.T) { } } +func TestCountDividers11(t *testing.T) { + for _, v := range vals { + got := CountDividers11(v.val) + if got != v.res { + t.Errorf("CountDividers11 test fails at %v with %v instead of %v\n", v.val, got, v.res) + } + } +} + func TestCountDividers2(t *testing.T) { for _, v := range vals { - got := CountDividers2(0, v.val) + got := CountDividers2(1, v.val) if got != v.res { t.Errorf("CountDividers2 test fails at %v with %v instead of %v\n", v.val, got, v.res) } } } +func TestCountDividers22(t *testing.T) { + for _, v := range vals { + got := CountDividers22(1, v.val) + if got != v.res { + t.Errorf("CountDividers22 test fails at %v with %v instead of %v\n", v.val, got, v.res) + } + } +} + func TestCountDividers3(t *testing.T) { for _, v := range vals { got := CountDividers3(v.val) @@ -50,3 +80,53 @@ func TestCountDividers3(t *testing.T) { } } +func TestCountDividers33(t *testing.T) { + for _, v := range vals { + got := CountDividers33(v.val) + if got != v.res { + t.Errorf("CountDividers33 test fails at %v with %v instead of %v\n", v.val, got, v.res) + } + } +} + +func BenchmarkCountDividers0(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers0(i) + } +} + +func BenchmarkCountDividers1(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers1(i) + } +} + +func BenchmarkCountDividers2(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers2(1, i) + } +} + +func BenchmarkCountDividers3(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers3(i) + } +} + +func BenchmarkCountDividers11(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers11(i) + } +} + +func BenchmarkCountDividers22(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers22(1, i) + } +} + +func BenchmarkCountDividers33(b *testing.B) { + for i := 1; i < b.N; i++ { + CountDividers33(i) + } +} -- 2.20.1