Jacobi symbol: Difference between revisions
Added 11l
(Added C code) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 12:
;Reference:
* [https://en.wikipedia.org/wiki/Jacobi_symbol Wikipedia article on Jacobi symbol].
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F jacobi(=a, =n)
I n <= 0
X ValueError(‘'n' must be a positive integer.’)
I n % 2 == 0
X ValueError(‘'n' must be odd.’)
a %= n
V result = 1
L a != 0
L a % 2 == 0
a /= 2
V n_mod_8 = n % 8
I n_mod_8 C (3, 5)
result = -result
(a, n) = (n, a)
I a % 4 == 3 & n % 4 == 3
result = -result
a %= n
I n == 1
R result
E
R 0
print(‘n\k|’, end' ‘’)
V kmax = 20
L(k) 0..kmax
print(‘#3’.format(k), end' ‘’)
print("\n----", end' ‘’)
L(k) 0..kmax
print(end' ‘---’)
print()
L(n) (1..21).step(2)
print(‘#<2 |’.format(n), end' ‘’)
L(k) 0..kmax
print(‘#3’.format(jacobi(k, n)), end' ‘’)
print()</lang>
{{out}}
<pre>
n\k| 0 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 1
3 | 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
5 | 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0
7 | 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1
9 | 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
11 | 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1
13 | 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1
15 | 0 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0
17 | 0 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1
19 | 0 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1
21 | 0 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1
</pre>
=={{header|AWK}}==
| |||