Basic arithmetic with C integers

class sage.rings.fast_arith.arith_int

Bases: object

gcd_int(a, b)[source]
inverse_mod_int(a, m)[source]
rational_recon_int(a, m)[source]

Rational reconstruction of a modulo m.

xgcd_int(a, b)[source]
class sage.rings.fast_arith.arith_llong

Bases: object

gcd_longlong(a, b)[source]
inverse_mod_longlong(a, m)[source]
rational_recon_longlong(a, m)[source]

Rational reconstruction of a modulo m.

EXAMPLES:

sage: from sage.rings.fast_arith import arith_llong
sage: arith_llong().rational_recon_longlong(1234567, 2147483629)
(-23606, 22613)

>>> from sage.all import *
>>> from sage.rings.fast_arith import arith_llong
>>> arith_llong().rational_recon_longlong(Integer(1234567), Integer(2147483629))
(-23606, 22613)

from sage.rings.fast_arith import arith_llong
arith_llong().rational_recon_longlong(1234567, 2147483629)
sage.rings.fast_arith.prime_range(start, stop=None, step=None, algorithm=None, py_ints=False)[source]

Return a list of all primes between start and stop - 1, inclusive (or between stop and start + 1 if step is negative).

If the second argument is omitted, this returns the primes up to the first argument.

See also

  • primes() is an alternative that uses less memory (but may be slower), because it returns an iterator, rather than building a list of the primes.

  • Primes can be used to create sets of primes with more complicated congruence conditions.

INPUT:

  • start – integer; lower bound (default: 1)

  • stop – integer; upper bound

  • step – integer or None (default: None); if not None, the function returns only primes that are congruent to start modulo step. If step is negative, then the returned list will be decreasing.

  • algorithm – string (default: None), one of:

    • None: Use algorithm 'pari_primes' if stop <= 436273009 (approximately 4.36E8). Otherwise use algorithm 'pari_isprime'.

    • 'pari_primes': Use PARI’s pari:primes function to generate all primes from 2 to stop. This is fast but may crash if there is insufficient memory. Raises an error if stop > 436273009.

    • 'pari_isprime': Wrapper for list(primes(start, stop)). Each (odd) integer in the specified range is tested for primality by applying PARI’s pari:isprime function. This is slower but will work for much larger input.

  • py_ints – boolean (default: False); return Python ints rather than Sage Integers (faster). Ignored unless algorithm 'pari_primes' is being used.

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(11, 100, 10)
[11, 31, 41, 61, 71]
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])
<class 'sage.rings.integer.Integer'>
sage: type(prime_range(8, algorithm='pari_isprime')[0])
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> prime_range(Integer(10))
[2, 3, 5, 7]
>>> prime_range(Integer(7))
[2, 3, 5]
>>> prime_range(Integer(2000), Integer(2020))
[2003, 2011, 2017]
>>> prime_range(Integer(2), Integer(2))
[]
>>> prime_range(Integer(2), Integer(3))
[2]
>>> prime_range(Integer(5), Integer(10))
[5, 7]
>>> prime_range(Integer(11), Integer(100), Integer(10))
[11, 31, 41, 61, 71]
>>> prime_range(-Integer(100), Integer(10), "pari_isprime")
[2, 3, 5, 7]
>>> prime_range(Integer(2), Integer(2), algorithm='pari_isprime')
[]
>>> prime_range(Integer(10)**Integer(16), Integer(10)**Integer(16)+Integer(100), "pari_isprime")
[10000000000000061, 10000000000000069, 10000000000000079, 10000000000000099]
>>> prime_range(Integer(10)**Integer(30), Integer(10)**Integer(30)+Integer(100), "pari_isprime")
[1000000000000000000000000000057, 1000000000000000000000000000099]
>>> type(prime_range(Integer(8))[Integer(0)])
<class 'sage.rings.integer.Integer'>
>>> type(prime_range(Integer(8), algorithm='pari_isprime')[Integer(0)])
<class 'sage.rings.integer.Integer'>

prime_range(10)
prime_range(7)
prime_range(2000, 2020)
prime_range(2, 2)
prime_range(2, 3)
prime_range(5, 10)
prime_range(11, 100, 10)
prime_range(-100, 10, "pari_isprime")
prime_range(2, 2, algorithm='pari_isprime')
prime_range(10**16, 10**16+100, "pari_isprime")
prime_range(10**30, 10**30+100, "pari_isprime")
type(prime_range(8)[0])
type(prime_range(8, algorithm='pari_isprime')[0])

Note

start and stop should be integers, but real numbers will also be accepted as input. In this case, they will be rounded to nearby integers start* and stop*, so the output will be the primes between start* and stop* - 1, which may not be exactly the same as the primes between start and stop - 1.

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)

  • Vincent Macri (added step option)