Jacobi symbol: Difference between revisions
add FreeBASIC
m (→{{header|Wren}}: Library name change.) |
(add FreeBASIC) |
||
Line 158:
=={{header|Factor}}==
The <code>jacobi</code> word already exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-jacobi%2Cmath.extras.html here].
=={{header|FreeBASIC}}==
<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
return gcdp( b, a mod b )
end function
function gcd(a as integer, b as integer) as uinteger
return gcdp( abs(a), abs(b) )
end function
function jacobi( a as uinteger, n as uinteger ) as integer
if gcd(a, n)<>1 then return 0
if a = 1 then return 1
if a>n then return jacobi( a mod n, n )
if a mod 2 = 0 then
if n mod 8 = 1 or n mod 8 = 7 then
return jacobi(a/2, n)
else
return -jacobi(a/2, n)
end if
end if
dim as integer q = (-1)^((a-1)/2 * (n-1)/2)
return q/jacobi(n, a)
end function
'print a table
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
dim as uinteger pn, k, prime(0 to 16) = {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}
dim as string outstr = " k "
for k = 1 to 36
outstr = outstr + padto(2, k)+" "
next k
print outstr
print " n"
for pn=0 to 16
outstr= " "+padto( 2, prime(pn) )+" "
for k = 1 to 36
outstr = outstr + padto(2, jacobi(k, prime(pn))) + " "
next k
print outstr
next pn</lang>
{{out}}
<pre> k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
n
3 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0
5 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1
7 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1
11 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1 -1 1 1
17 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1
19 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 -1 -1 0 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 1 0 1 -1 -1 1 1 1 1
31 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 0 1 1 -1 1 1
37 1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1
41 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 1
43 1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1
47 1 1 1 1 -1 1 1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 1 -1 1 -1 1
53 1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1
59 1 -1 1 1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 1
61 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1</pre>
=={{header|Go}}==
| |||