Anonymous user
Jacobi symbol: Difference between revisions
→{{header|Nim}}
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 883:
return if (n == 1) result else 0
}</lang>
=={{header|Nim}}==
Translation of the Lua program from Wikipedia page.
<lang Nim>template isOdd(n: int): bool = (n and 1) != 0
template isEven(n: int): bool = (n and 1) == 0
func jacobi(n, k: int): range[-1..1] =
assert k > 0 and k.isOdd
var n = n mod k
var k = k
result = 1
while n != 0:
while n.isEven:
n = n shr 1
if (k and 7) in [3, 5]:
result = -result
swap n, k
if (n and 3) == 3 and (k and 3) == 3:
result = -result
n = n mod k
if k != 1: result = 0
when isMainModule:
import strutils
stdout.write "n/k|"
for n in 1..20:
stdout.write align($n, 3)
echo '\n' & repeat("—", 64)
for k in countup(1, 21, 2):
stdout.write align($k, 2), " |"
for n in 1..20:
stdout.write align($jacobi(n, k), 3)
echo ""</lang>
{{out}}
<pre>n/k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
————————————————————————————————————————————————————————————————
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 | 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
5 | 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0
7 | 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1
9 | 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
11 | 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1
13 | 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1
15 | 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0
17 | 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1
19 | 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1
21 | 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1</pre>
=={{header|Perl}}==
| |||