# 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: 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)

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