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=None, py_ints=False)

Return a list of all primes between start and stop - 1, inclusive.

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

The sage command 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.

INPUT:

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

• stop – integer, upper bound

• algorithm – optional 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 – optional boolean (default False), return Python ints rather than Sage Integers (faster). Ignored unless algorithm "pari_primes" is being used.

EXAMPLES:

Sage

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])
<class 'sage.rings.integer.Integer'>
sage: type(prime_range(8,algorithm="pari_isprime")[0])
<class 'sage.rings.integer.Integer'>

Python

>>> 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(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'>

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)