number_utils.hpp

Go to the documentation of this file.

#ifndef NUMBER_UTILS_H
#define NUMBER_UTILS_H
 
#include <concepts>
#include <cmath>
#include <vector>
#include <array>
#include <cstdint>
 
namespace hsc_snippets {
    template<std::integral T>
    int numDigits(T num) {
        int cnt = 0;
        while (num != 0) {
            cnt += 1;
            num /= 10;
        }
        return cnt;
    }
 
    template<std::integral T>
    int numBits(T num) {
        if (num < 0) {
            return sizeof(T) << 3;
        }
        int cnt = 0;
        while (num != 0) {
            cnt += 1;
            num = num >> 1;
        }
        return cnt;
    }
 
    static std::vector<int> SieveOfEratosthenes(int n) {
        // Initialize a boolean vector "prime" with entries up to n. All entries are initially set to true.
        // A value in prime[i] will be false if i is not a prime number, and true if it is a prime number.
        std::vector<bool> prime(n + 1, true);
        prime[0] = prime[1] = false; // 0 and 1 are not considered prime numbers.
 
        // This vector will store all the prime numbers found.
        std::vector<int> primes;
 
        // Start iterating from the first prime number, 2, up to the square root of n.
        // We only need to go up to sqrt(n) because if n has a divisor greater than sqrt(n),
        // it must also have a smaller one, so all composites will have been marked by this point.
        for (int p = 2; p <= std::sqrt(n); ++p) {
            // If prime[p] is true, then it is a prime number.
            if (prime[p]) {
                // Mark all multiples of p starting from p^2 as not prime.
                // Starting from p^2 because all smaller multiples of p would have already been marked by smaller primes.
                for (int i = p * p; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }
 
        // Collect all prime numbers: iterate over the range up to n and
        // add the number to the primes list if its corresponding value in the prime vector is true.
        for (int p = 2; p <= n; ++p) {
            if (prime[p]) {
                primes.push_back(p);
            }
        }
 
        // Return the vector containing all the primes found.
        return primes;
    }
 
    static bool isPerfectSquare(std::int32_t num) {
        if (num < 0) {
            return false;
        }
        constexpr std::array<std::int32_t, 46341> arr = []()constexpr {
            std::array<std::int32_t, 46341> _arr = {};
            for (int i = 0; i < 46341; ++i) {
                _arr[i] = i * i;
            }
            return _arr;
        }();
 
        return std::binary_search(arr.begin(), arr.end(), num);
    }
}
 
#endif // NUMBER_UTILS_H