1 /* 2 Copyright (C) 2009 William Hart 3 Copyright (C) 2014, 2015 Dana Jacobsen 4 5 This file is part of FLINT. 6 7 FLINT is free software: you can redistribute it and/or modify it under 8 the terms of the GNU Lesser General Public License (LGPL) as published 9 by the Free Software Foundation; either version 2.1 of the License, or 10 (at your option) any later version. See <https://www.gnu.org/licenses/>. 11 */ 12 13 #include <gmp.h> 14 #include "flint.h" 15 #include "ulong_extras.h" 16 n_is_prime(mp_limb_t n)17int n_is_prime(mp_limb_t n) 18 { 19 /* flint's "BPSW" checked against Feitsma and Galway's database [1, 2] 20 up to 2^64 by Dana Jacobsen. 21 [1] http://www.janfeitsma.nl/math/psp2/database 22 [2] http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html 23 */ 24 25 if (n < 11) { 26 if (n == 2 || n == 3 || n == 5 || n == 7) return 1; 27 else return 0; 28 } 29 if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; 30 if (n < 121) /* 11*11 */ return 1; 31 if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || 32 !(n%23) || !(n%29) || !(n%31) || !(n%37) || 33 !(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; 34 if (n < 3481) /* 59*59 */ return 1; 35 if (n > 1000000 && 36 (!(n% 59) || !(n% 61) || !(n% 67) || !(n% 71) || !(n% 73) || 37 !(n% 79) || !(n% 83) || !(n% 89) || !(n% 97) || !(n%101) || 38 !(n%103) || !(n%107) || !(n%109) || !(n%113) || !(n%127) || 39 !(n%131) || !(n%137) || !(n%139) || !(n%149))) return 0; 40 41 return n_is_probabprime(n); 42 } 43