Euclid  
gcd(a, b) Evaluates to the greatest common denominator of integers a and b. This is the largest integer that divides both a and b. lcm(a, b) Evaluates to the least common multiple of integers a and b. This is the smallest number such that both a and b divide the number. isPrime(p) Returns 1 if p is prime, 0 if not. This function may take a while for large p. isProbablyPrime(p, c) Returns 1 if p is probably prime, 0 if not. In particular, if this returns 1 then the probability that n is prime exceeds 1  1/(2^c). If this returns 0 it means that p is definitely not prime. c must be a positive integer less than 2^32. totient(n) Returns the Euler totient of n, which is the number of positive integers less than n which are relatively prime to n. For example, totient(9) = 6 since 1, 2, 4, 5, 7, and 8 are relatively prime to 9. nextPrime(n) Returns the smallest prime larger than n. n must be a positive integer. This function may take a while for large n. nearestPrime(n) Returns a prime p such that p = n +/ d, d >= 0, which minimizes d. In other words, if n is prime then the function will return n. Otherwise, It will return the prime nearest to n. If there are two candidates, then it will return the larger of the two numbers. For example, nearestPrime(15) will return 17 even though 13 is just as close. nearestProbablePrime(n, c) Like nearestPrime(), but returns the number closest to n (including n) which is prime with probability 1  1/(2^c). c must be a positive integer less than 2^32. This function may take a while for large c. nextProbablePrime(n, c) Returns the smallest probable prime larger than n. n must be a positive integer. c must be a positive integer less than 2^32. The returned value is prime with probability 1  1/(2^c). This function may take a while for large c. nthPrime(n) Returns the nth prime. 2 is the 1st prime, 3 is the 2nd prime, etc. properFactors(x) Returns the set of proper factors of x (does not include 1 or x). primeFactors(x) Returns the set of prime factors of x. 
Euclid 
Copyright © 20032006 Kevin L. Gong

