blob: d7843b45833359c577f61bdd597ba7cf1f99c1f9 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include "NumberHelpers.h"
bool isEven(int x) {
return x % 2 == 0;
}
// The following functions are taken from my own Interval task solution
bool isPowerOfTwo(int x)
{
return x > 0 && // No (normal) power of 2 creates negatives or 0
(x & (x - 1)) == 0; // Thanks https://stackoverflow.com/a/600306/12036073, original implementation was a lot less efficient
}
bool isPrime(int num) // Forked from my own implementation - https://gitlab.com/Syndamia/algorithms/-/blob/master/C/IsPrime.c
{
if (num < 0) num *= -1; // This is required, since we calculate sqrt(num)
if (num == 2 || num == 3 || num == 5 || num == 7 || num == 11 || num == 13)
return true;
// A lot of numbers are divisible by these ones, so we're going to do a bit of simple optimization
if (num == 0 || num == 1 || num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 || num % 11 == 0 || num % 13 == 0)
return false;
// All primes follow the formula 6n +- 1 (where n >= 1). Since we've already checked up to 13, we're going to
// start with 18 - 1 = 17. Also using root of number to eliminate a lot of checks.
// Primary source: https://en.wikipedia.org/wiki/Primality_test#Simple_methods
for (int i = 18, root = sqrt(num); i - 1 <= root; i += 6)
{
if (num % (num - 1) == 0 || num % (num + 1) == 0)
return false;
}
return true;
}
|
