Tau function: Difference between revisions
(Added Go) |
(→{{header|Go}}: More idiomatic.) |
||
| Line 19: | Line 19: | ||
func countDivisors(n int) int { |
func countDivisors(n int) int { |
||
count := 0 |
|||
i := 1 |
|||
k := 2 |
|||
if n%2 == 0 { |
if n%2 == 0 { |
||
k = 1 |
k = 1 |
||
Revision as of 19:19, 20 December 2020
Given a positive integer, count the number of its positive divisors.
- Task
Show the result for the first 100 positive integers.
- Related task
Go
<lang go>package main
import "fmt"
func countDivisors(n int) int {
count := 0
i := 1
k := 2
if n%2 == 0 {
k = 1
}
for i*i <= n {
if n%i == 0 {
count++
j := n / i
if j != i {
count++
}
}
i += k
}
return count
}
func main() {
fmt.Println("The tau functions for the first 100 positive integers are:")
for i := 1; i <= 100; i++ {
fmt.Printf("%2d ", countDivisors(i))
if i%20 == 0 {
fmt.Println()
}
}
}</lang>
- Output:
The tau functions for the first 100 positive integers are: 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9
Python
Using prime factorization
<lang Python>def factorize(n):
assert(isinstance(n, int))
if n < 0:
n = -n
if n < 2:
return
k = 0
while 0 == n%2:
k += 1
n //= 2
if 0 < k:
yield (2,k)
p = 3
while p*p <= n:
k = 0
while 0 == n%p:
k += 1
n //= p
if 0 < k:
yield (p,k)
p += 2
if 1 < n:
yield (n,1)
def tau(n):
assert(n != 0)
ans = 1
for (p,k) in factorize(n):
ans *= 1 + k
return ans
if __name__ == "__main__":
print([tau(n) for n in range(1,101)])</lang>
Finding divisors efficiently
<lang Python>def tau(n):
assert(isinstance(n, int) and 0 < n)
ans, i, j = 0, 1, 1
while i*i <= n:
if 0 == n%i:
ans += 1
j = n//i
if j != i:
ans += 1
i += 1
return ans
if __name__ == "__main__":
print([tau(n) for n in range(1,101)])</lang>
- Output:
[1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9]
REXX
<lang rexx>/*REXX program counts the number of divisors (tau, or sigma_0) up to and including N.*/ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 100 /*Not specified? Then use the default.*/ say 'the number of divisors (tau) for integers up to ' n " (inclusive):"; say say '─index─' center(" tau (number of divisors) ", 80, '─') w= max(7, length(n) ) /*W: used to align 1st output column. */ $= /*$: the output list, shown 20/line. */
do j=1 for n /*list # proper divisors (tau) 1 ──► N */
$= $ || right( tau(j), 4) /*add a tau number to the output list. */
if j//20\==0 then iterate /*Not a multiple of 20? Don't display.*/
say center(j-19, 7) $; $= /*display partial list to the terminal.*/
end /*j*/
if $\== then say center(j-1, 7) $ /*any residuals left to display ? */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tau: procedure; parse arg x 1 y /*X and $ are both set from the arg.*/
if x<6 then return 2 + (x==4) - (x==1) /*some low #s should be handled special*/
odd= x // 2 /*check if X is odd (remainder of 1).*/
if odd then do; #= 2; end /*Odd? Assume divisor count of 2. */
else do; #= 4; y= x % 2; end /*Even? " " " " 4. */
/* [↑] start with known number of divs*/
do j=3 for x%2-3 by 1+odd while j<y /*for odd number, skip even numbers. */
if x//j==0 then do /*if no remainder, then found a divisor*/
#= # + 2; y= x % j /*bump # of divisors; calculate limit.*/
if j>=y then do; #= # - 1; leave; end /*reached limit?*/
end /* ___ */
else if j*j>x then leave /*only divide up to √ x */
end /*j*/ /* [↑] this form of DO loop is faster.*/</lang>
- output when using the default input:
the number of divisors (tau) for integers up to 100 (inclusive): ─index─ ─────────────────────────── tau (number of divisors) ─────────────────────────── 1 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 21 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 41 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 61 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 81 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
System.print("The tau functions for the first 100 positive integers are:") for (i in 1..100) {
Fmt.write("$2d ", Int.divisors(i).count)
if (i % 20 == 0) System.print()
}</lang>
- Output:
The tau functions for the first 100 positive integers are: 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9