primes.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file common/sigmaodd/primes.hpp (January 5, 2018)
 * \brief
 * Functions to access to tables of precaculated prime numbers
 * and offsets to iterate on possible prime numbers.
 *
 * By default a table of all primes < 2^28 is used.
 * This table must be read from the binary file big_data/prime28.bin.
 *
 * If the macro PRIME16 is defined
 * then a little table of all primes < 2^16 is used.
 * This table is automatically included by the compilation.
 *
 * If the macro PRIME16 is defined
 * then there are also a table of offset to iterate on possible primes.
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

#ifndef PROGS_SRC_COMMON_SIGMAODD_PRIMES_HPP_
#define PROGS_SRC_COMMON_SIGMAODD_PRIMES_HPP_

// \cond
#include <cstdint>

#include <string>
#include <vector>
// \endcond

#include "divisors.hpp"



// If defined the table of primes contains all odd prime numbers < 2^16 instead < 2^28.
// #define PRIME16



namespace sigmaodd {

  /* ******
   * Type *
   ********/

  /** \brief
   * Type for prime number, particularly for the table of primes.
   */
  typedef uint32_t prime_type;



  /* ***********
   * Constants *
   *************/

#ifdef PRIME16
  /** \brief
   * Modulo used for offsets to jump to one potential prime number to next.
   */
  constexpr nat_type array_potential_prime_offsets_modulo_ = 210;  // = 2*3*5*7
#endif


#ifdef PRIME16
  /** \brief
   * Number of offset values in the table array_potential_prime_offsets_.
   */
  constexpr unsigned int array_potential_prime_offsets_nb_ = 48;
#endif


  /** \brief
   * Number of *odd* prime numbers in the table array_odd_primes_.
   *
   * https://primes.utm.edu/nthprime/
   * 14630841th prime (with 2): 268435361
   * 14630842th prime (with 2): 268435367
   * 14630843th prime (with 2): 268435399 < 2^28
   * 14630844th prime (with 2): 268435459 > 2^28
   */
#ifdef PRIME16
  constexpr unsigned int array_odd_primes_nb_ = 6542 - 1;  // all odd primes < 2^16
#else
  constexpr unsigned int array_odd_primes_nb_ = 14630843u - 1;  // all odd primes < 2^28
  // constexpr unsigned int array_odd_primes_nb_ = 203280221u - 1;  // all odd primes < 2^32
#endif


#ifdef PRIME16
  /** \brief
   * Array of offsets to jump to one potential prime number to next.
   * See potential_prime_offsets_table_by_index().
   */
  extern const nat_type array_potential_prime_offsets_[array_potential_prime_offsets_nb_];
#endif


  /** \brief
   * Default filename for the binary file "big_data/prime28.bin".
   */
  extern const std::string prime_filename;



  /* **********
   * Variable *
   ************/
  /** \brief
   * Array of all *odd* prime numbers < 2^28 with a final 0.
   * (Or < 2^16 if the macro PRIME16 is defined.)
   */
#ifdef PRIME16
  extern const prime_type array_odd_primes_[array_odd_primes_nb_ + 1];
#else
  extern prime_type* array_odd_primes_;
#endif



  /* ************
   * Prototypes *
   **************/

  /** \brief
   * Return a list of prime factors with their exponents.
   *
   * @param n != 0 <= MAX_POSSIBLE_N
   */
  std::vector<FactorExp>
  factorize(nat_type n);


  /** \brief
   * Return the number corresponding to the factorization.
   *
   * @param prime_exps list of primes numbers with their exponent such that the corresponding number is not too big for nat_type
   */
  nat_type
  factorization_to_n(std::vector<FactorExp> prime_exps);


  /** \brief
   * Return the number of all divisors of the number corresponding to the factorization.
   *
   * @param prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type
   */
  nat_type
  factorization_to_nu(std::vector<FactorExp> prime_exps);


  /** \brief
   * Return the number of odd divisors of the number corresponding to the factorization.
   *
   * @param prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type
   */
  nat_type
  factorization_to_nu_odd(std::vector<FactorExp> prime_exps);


  /** \brief
   * Return the sum of all divisors of the number corresponding to the factorization.
   *
   * @param prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type
   */
  nat_type
  factorization_to_sigma(std::vector<FactorExp> prime_exps);


  /** \brief
   * Return the sum of odd divisors of the number corresponding to the factorization.
   *
   * @param prime_exps list of distinct primes numbers with their exponent such that the corresponding number is not too big for nat_type
   */
  nat_type
  factorization_to_sigma_odd(std::vector<FactorExp> prime_exps);


  /** \brief
   * Return true iff n is a prime number
   */
  bool
  is_prime(nat_type n);


  /** \brief
   * Return true iff n is a prime number present in the precalculated table.
   */
  bool
  is_prime_in_odd_primes_table(nat_type n);


  /** \brief
   * Return the (i + 1)th odd prime number from the precalculated table.
   *
   * @param i 0 <= i < odd_primes_table_nb()
   *
   * @return the item of index i of the odd primes table
   */
  inline
  prime_type
  odd_primes_table_by_index(unsigned int i);


  /** \brief
   * Return the last odd prime number in the precalculated table.
   */
  inline
  prime_type
  odd_primes_table_last();


  /** \brief
   * Return the number of odd prime numbers in the precalculated table.
   */
  constexpr
  unsigned int
  odd_primes_table_nb();


  /** \brief
   * Return a pointer to the first number in the precalculated table.
   */
  inline
  const prime_type*
  odd_primes_table_ptr();


#ifdef PRIME16
  /** \brief
   * Return the item of index i of the potential prime offsets table.
   *
   * @param i 0 <= i < potential_prime_offsets_table_nb
   *
   * @return the item of index i of the potential prime offsets table
   */
  inline
  nat_type
  potential_prime_offsets_table_by_index(unsigned int i);
#endif


#ifdef PRIME16
  /** \brief
   * Return the modulo used by the potential prime offsets table
   */
  constexpr
  nat_type
  potential_prime_offsets_table_modulo();
#endif


#ifdef PRIME16
  /** \brief
   * Return the number of offsets in the potential prime offsets table
   */
  constexpr
  unsigned int
  potential_prime_offsets_table_nb();
#endif


  /** \brief
   * Read the binary file prime_filename
   * to fill the table with all primes < 2^28.
   * This table must be read from the binary file big_data/prime28.bin.
   *
   * If prime_filename is not available in the same directory
   * then search it in parents directories.
   *
   * If the macro PRIME16 is defined
   * the this function do nothing.
   *
   * @return true iff the file was completely loaded
   */
  bool
  read_primes_table();

}  // namespace sigmaodd

#include "primes__inline.hpp"

#endif  // PROGS_SRC_COMMON_SIGMAODD_PRIMES_HPP_