Jacobi symbol: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 883: | Line 883: | ||
return if (n == 1) result else 0 |
return if (n == 1) result else 0 |
||
}</lang> |
}</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}}== |
=={{header|Perl}}== |