Name

number_isprime — Checks if a number is prime.

Calling Sequence

   isprime = number_isprime ( n )
   [ isprime , status ] = number_isprime ( n )
   [ isprime , status ] = number_isprime ( n , method )
   [ isprime , status ] = number_isprime ( n , method , imax )
   [ isprime , status ] = number_isprime ( n , method , imax , verbose )
   
   

Parameters

n :

a 1x1 matrix of floating point integers, must be positive

method :

a 1x1 matrix of strings, the algorithm to use, default method = "6k"

imax :

a 1-by-1 matrix of floating point integers, the number of steps in the loop (default imax=10000)

verbose :

a 1-by-1 matrix of booleans, set to true to display messages (default verbose=%f)

isprime :

a 1x1 matrix of booleans, isprime=%t if n is prime, isprime=%f if not.

status :

a 1x1 matrix of booleans, status=%t if the test performed completely, status=%f if the test failed

Description

Returns %t if the given number is prime. If status is %t, then

  • isprime is true if n is prime.
  • isprime is false if n is not prime.

If status is %f, then the primality test failed.

Any input argument equal to the empty matrix is replaced by its default value.

The following values of method are available.

"modulo"

Uses the modulo function.

"6k"

Based on modulo function and on the fact that prime numbers are of the form 6k + 1, 6k - 1. The sequence of divisors to test is : 5, 7, 11, 13, 17, 19, ...

"30k"

Based on modulo function and on the fact that prime numbers are of the form 30k + i, with i = 1, 7, 11, 13, 17, 19, 23, 29. Notice that the primorial function for n = 5 is equal to c#(5) = 2*3*5 = 30 The numbers 1,7,11,...,29 are the ones so that gcd(i,30)=1 We must first test for n = 2, 3 or 5.

"210k"

Based on modulo function and on the fact that prime numbers are of the form 210k + i, with i = 1 11 13 17 ... 179 181 187 191 193 197 199 209 We have c#(7) = 210. The numbers 1,11,...,209 are the ones so that gcd(i,210)=1 We must first test for n = 2, 3 or 5 or 7. This test may perform well (i.e. fast) in the case where the number is very large.

"primes"

Based on number_primes function : if the last number is equal to n, then the number is prime.

"massdivide"

Based on a massive division of n by all odd numbers up to sqrt(n). This is fast, but requires all lot of memory if the number is large.

Examples

// Check simple examples
isprime = number_isprime(0) // %f
isprime = number_isprime(1) // %f
isprime = number_isprime(2) // %t
isprime = number_isprime(7) // %t
isprime = number_isprime(10) // %f

// Configure imax
// Success:
isprime = number_isprime(1013,[],1000)
// Generates an error (not enough iterations):
isprime = number_isprime(1013,[],2)

// Use verbose option
number_isprime(1013,[],[],%t)

// A loop on some values
algos = ["primes"
"modulo"
"6k"
"30k"
"210k"
"massdivide"
]
mprintf("   primes, modulo, 6k, 30k, 210k, massdivide\n");
for n = 1 : 20
msg="";
msg=msg+msprintf("n=%d ",n);
for method = algos'
isprime = number_isprime(n,method);
msg=msg+msprintf("%s ",string(isprime));
end
msg=msg+msprintf("\n");
mprintf("%s\n",msg);
end

   

Authors

Copyright (C) 2009 - 2010 - DIGITEO - Michael Baudin