Trial Factorisation

From CodeCodex

Related content:

Algorithm[edit]

We can test if a number is prime by testing if it has any divisors apart from itself and one. If it does then it is composite and not prime. The list of trial divisors must include all primes less or equal to the square root of the target number, but can also include composite numbers. Negative numbers, zero and one are not prime by definition, the smallest prime number is two.

Implementations[edit]

C++[edit]

// Trial Factorisation primality test  
bool isPrime(int num) {
    // Negatives, zero and one are not prime
    if (num < 2) { return false; }

    // Remove multiples of two and three
    switch (num % 6) {
        case 0: return false;
        case 1: break;
        case 2: return 2 == num;
        case 3: return 3 == num;
        case 4: return false;
        case 5: break;
    } // end switch

    // Look for factors of 5, 7 etc.
    int trialFac  = 5;                 // Current trial factor
    int increment = 2;                 // Increment for trial factor (2 and 4 alternating)
    int sqrtNum   = isqrt(num);        // Integer square root of number, see separate algorithm
    while (trialFac <= sqrtNum) {
        // Check num against current trial factor
        if (0 == (num % trialFac)) { return false; }

        // Go to next trial factor
        trialFac += increment;          // Next trial factor
        increment = 6 - increment;      // Add 2, 4 alternating
    } // end while

    return true;                        // number is prime if we reach here
} // end isPrime()

This version of Trial Factorisation uses a 2-4 wheel: starting from 5 add 2 and 4 alternately. This gives a sequence of numbers containing all the primes from 5 and no multiples of two or three. If your system already has a list of all the primes up to the square root of the largest number you want to test then use that to find the next trial factor.

Erlang[edit]

is_prime(N) when N < 2 -> false;
is_prime(N) when N =:= 2; N =:= 3 -> true;
is_prime(N) when N rem 2 =:= 0; N rem 3 =:= 0 -> false;
is_prime(N) ->
    Limit = isqrt(N),           % integer square root of number
    is_prime(N, 5, Limit, 2).

is_prime(_, I, Limit, _) when I > Limit     -> true;
is_prime(N, I,     _, _) when N rem I =:= 0 -> false;
is_prime(N, I, Limit, Inc) ->
    is_prime(N, I+Inc, Limit, 6-Inc).

F#[edit]

Similar to the OCaml but using an auxiliary function to evade the lack of optional arguments:

> let rec is_prime_aux m n =
    m * m > n || n mod m <> 0 && is_prime_aux (m+1) n;;
val is_prime_aux : int -> int -> bool
> let is_prime = is_prime_aux 2 n;;
val is_prime : int -> bool

OCaml[edit]

This version of Trial Factorisation simply tests each divisor from 2 upwards to see if the given number is exactly divisible by it:

# let rec is_prime ?(m=2) n =
    m * m > n || n mod m <> 0 && is_prime ~m:(m+1) n;;
val is_prime : ?m:int -> int -> bool = <fun>

For example, filtering out prime numbers from a list:

# List.filter is_prime [2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19];;
- : int list = [2; 3; 5; 7; 11; 13; 17; 19]

Ruby[edit]

class Integer
  def prime?
    return false  if self < 2
    return true   if self == 2 or self == 3
    return false  if self%2 == 0 or self%3 == 0
    limit = Math.sqrt(self).to_i
    5.step(limit, 2) do |i|
      return false  if self%i == 0
    end
    true
  end
end

Scheme[edit]

This version of Trial Factorisation simply tests each divisor from 2 upwards to see if the given number is exactly divisible by it:

(define (is-prime n)
  (let loop ((m 2))
    (cond ((> (* m m) n) #t)
          ((= (modulo n m) 0) #f)
          (else (loop (+ m 1))))))