bzr branch
http://gegoxaren.bato24.eu/bzr/simpletypesystem/trunk
|
150
by Gustav Hartvigsson
* Fixed the tests in the CMake file |
1 |
#include "primes.h" |
2 |
#include "defs.h" |
|
3 |
#include "utils.h" |
|
4 |
||
5 |
||
6 |
sboolean
|
|
7 |
s_prime_is (suint n) { |
|
8 |
|
|
9 |
|
|
10 |
if (n <= 1 || (n % 2 == 0 && n > 2) ) { |
|
11 |
return FALSE; |
|
12 |
} |
|
13 |
|
|
14 |
/* |
|
15 |
* Binary search in list.
|
|
16 |
*/
|
|
17 |
if (n <= 4999) { |
|
18 |
return s_binary_search (SPrimeListLong, 0, S_PRIME_LIST_LONG_LEN, n); |
|
19 |
} |
|
20 |
|
|
21 |
/* |
|
22 |
* Since all non-primes are a product of two primes, we only need to check
|
|
23 |
* a subset of all values.
|
|
24 |
*/
|
|
25 |
for (sint i = 0; i < S_PRIME_LIST_LONG_LEN; i++){ |
|
26 |
if (n % SPrimeListLong[i] == 0) { |
|
27 |
return FALSE; |
|
28 |
} |
|
29 |
} |
|
30 |
/* |
|
31 |
* if we exit the loop now, and n is less than the highest value in the list
|
|
32 |
* squared, we have found a prime.
|
|
33 |
*/
|
|
34 |
if (n <= 4999 * 4999 ) { |
|
35 |
return TRUE; |
|
36 |
} |
|
37 |
|
|
38 |
/* |
|
39 |
* Last chance to see if it is not a prime. This will be expensive!
|
|
40 |
*/
|
|
41 |
for (sint i = 4999 + 1; i <= floor(sqrt(n)); i++) { |
|
42 |
if (n % i == 0) { |
|
43 |
return FALSE; |
|
44 |
} |
|
45 |
} |
|
46 |
|
|
47 |
return TRUE; |
|
48 |
}
|