Basic arithmetic with C integers¶
-
class
sage.rings.fast_arith.
arith_int
¶ Bases:
object
-
gcd_int
(a, b)¶
-
inverse_mod_int
(a, m)¶
-
rational_recon_int
(a, m)¶ Rational reconstruction of a modulo m.
-
xgcd_int
(a, b)¶
-
-
class
sage.rings.fast_arith.
arith_llong
¶ Bases:
object
-
gcd_longlong
(a, b)¶
-
inverse_mod_longlong
(a, m)¶
-
rational_recon_longlong
(a, m)¶ Rational reconstruction of a modulo m.
-
-
sage.rings.fast_arith.
prime_range
(start, stop=None, algorithm='pari_primes', py_ints=False)¶ Return a list of all primes between
start
andstop - 1
, inclusive.If the second argument is omitted, this returns the primes up to the first argument.
This function is closely related to (and can use) the primes iterator. Use algorithm
"pari_primes"
when bothstart
andstop
are not too large, since in all cases this function makes a table of primes up tostop
. If both are large, use algorithm"pari_isprime"
instead.Algorithm
"pari_primes"
is faster for most input, but crashes for larger input. Algorithm"pari_isprime"
is slower but will work for much larger input.INPUT:
start
– integer, lower boundstop
– integer, upper boundalgorithm
– optional string, one of:"pari_primes"
: Uses PARI’s pari:primes function.Generates all primes up to stop. Depends on PARI’s pari:primepi function.
“pari_isprime”: Uses a mod 2 wheel and PARI’s pari:isprime function by calling the primes iterator.
py_ints
– optional boolean (defaultFalse
), return Python ints rather than Sage Integers (faster)
EXAMPLES:
sage: prime_range(10) [2, 3, 5, 7] sage: prime_range(7) [2, 3, 5] sage: prime_range(2000,2020) [2003, 2011, 2017] sage: prime_range(2,2) [] sage: prime_range(2,3) [2] sage: prime_range(5,10) [5, 7] sage: prime_range(-100,10,"pari_isprime") [2, 3, 5, 7] sage: prime_range(2,2,algorithm="pari_isprime") [] sage: prime_range(10**16,10**16+100,"pari_isprime") [10000000000000061, 10000000000000069, 10000000000000079, 10000000000000099] sage: prime_range(10**30,10**30+100,"pari_isprime") [1000000000000000000000000000057, 1000000000000000000000000000099] sage: type(prime_range(8)[0]) <type 'sage.rings.integer.Integer'> sage: type(prime_range(8,algorithm="pari_isprime")[0]) <type 'sage.rings.integer.Integer'>
AUTHORS:
William Stein (original version)
Craig Citro (rewrote for massive speedup)
Kevin Stueve (added primes iterator option) 2010-10-16
Robert Bradshaw (speedup using Pari prime table, py_ints option)