iconEuler Reference

Integer Arithmetic

Integer factorization and modulo functions.

function gcd (a:integer, b:integer)

  Computes the greatest common divisor of a and b.
  See also: primes, isprime, factor, lcm, mod, invmod, ggt.
function lcm (a,b)

  Returns least common multiple of a and b.
  See also: primes, isprime, factor, gcd, mod, invmod, ggt.
function ggt (x:integer, y:integer)

  Return {g,a,b} such that ax+by=g.
  
  >p=23423429; isprime(p)
  1
  >x=3423; {g,a,b}=ggt(x,p);> a,
  4831125
  >mod(a*x,p)
  1
  
  See also: primes, isprime, factor, gcd, lcm, mod, invmod.
function invmod (x:integer, m:integer)

  Return y such that x*y is 1 modulo m.
  
  >p=23423429; invmod(3423,p)
  4831125
  See also: primes, isprime, factor, gcd, lcm, mod, ggt.
function primes (n:integer)

  Return all primes up to n using the Sieve of Erastothenes.
  
  >length(primes(100000))
  9592
  
  For this, I have demonstrated a native implementation in C.
  
  See also: isprime, factor, gcd, lcm, mod, invmod, ggt.
function isprime (n:integer)

  Returns true if n is a prime number, false otherwise.
  See also: primes, factor, gcd, lcm, mod, invmod, ggt.
function factor (n:integer, p=none)

  Returns prime factorization of n. If n==1, returns 1.
  See also: primes, isprime, gcd, lcm, mod, invmod, ggt.

Documentation Homepage