primes.h

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025  Medusa Slockbower
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <https://www.gnu.org/licenses/>.
// =====================================================================================================================
 
#ifndef FENNEC_MATH_EXT_PRIMES_H
#define FENNEC_MATH_EXT_PRIMES_H
 
#include <fennec/math/exponential.h>
 
namespace fennec
{
 
template<typename genType>
constexpr bool is_prime(genType x) {
    // Base Cases Covers
    if (x <= 1)                   return false; // Eliminates 0 and 1
    if (x <= 3)                   return true;  // Eliminates 2 and 3
    if (x % 2 == 0 or x % 3 == 0) return false; // Eliminates even numbers and numbers divisible by 3
    // 4, 6, 8, 9, 10, 12, 14, 15
    if (x < 15)                   return true;  // Covers 5, 7, 11, 13
 
    // Due to the property of 15 being divisible by 5 and the nature of primes
    // All prime numbers must end in 1, 3, 7, 9
    // when x/15 is even, x%15 must be odd
    // and when x/15 is odd, x%15 must be even
    // To explain, when x/15 is even, 15*x/15 ends in 0, and when odd, ends in 5
    // Thus when x/15 is even, 15*x/15 ends in 0, and the results are 1, 3, 7, 11, 13
    // And  when x/15 is even, 15*x/15 ends in 5, and the results are 2, 4, 8, 14
    genType mod15 = x % 15;
    genType mod15e = mod15 % 2;
    genType div15e = (x / 15) % 2;
    if (mod15e == div15e) return false;
 
    // Iterate
    genType limit = sqrt(x);
    for (genType i = 5; i <= limit; i += 6) {
        if (x % i == 0 || x % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}
 
template<typename genType>
constexpr genType next_prime(genType x) {
    genType n = (x + 1) / 6 + 1;
 
    while (true) {
        x = (n++ * 6) - 1;
        if (fennec::is_prime(x)) return x;
        if (fennec::is_prime(x += 2)) return x;
    }
}
 
template<typename genType>
constexpr genType next_prime2(genType x) {
    genType n = (x + 1) / 6;
    n *= 2;
 
    while (true) {
        x = (n++ * 6) - 1;
        if (fennec::is_prime(x)) return x;
        if (fennec::is_prime(x += 2)) return x;
    }
}
 
template<typename genType>
constexpr genType prev_prime(genType x) {
    genType n = (x + 1) / 6 - 1;
 
    while (true) {
        x = (n-- * 6) - 1;
        if (fennec::is_prime(x)) return x;
        if (fennec::is_prime(x += 2)) return x;
    }
}
 
template<typename genType>
constexpr genType prev_prime2(genType x) {
    genType n = (x + 1) / 6;
    n /= 2;
 
    while (true) {
        x = (n-- * 6) - 1;
        if (fennec::is_prime(x)) return x;
        if (fennec::is_prime(x += 2)) return x;
    }
}
 
}
 
#endif // FENNEC_MATH_EXT_PRIMES_H