sieves.h

Go to the documentation of this file.

#pragma once
 
 
#include <inttypes.h>
#include <stdlib.h>
 
#include <nut/modular_math.h>
#include <nut/factorization.h>
 
NUT_ATTR_CONST
uint64_t nut_max_prime_divs(uint64_t max);
 
NUT_ATTR_CONST
uint64_t nut_max_primes_le(uint64_t max);
 
NUT_ATTR_CONST
NUT_ATTR_NONNULL(1)
NUT_ATTR_RETURNS_NONNULL
NUT_ATTR_ACCESS(none, 1)
static inline void *nut_Pitcharr_get(void *buf, size_t pitch, uint64_t i){
    return buf + i*pitch;
}
 
NUT_ATTR_PURE
NUT_ATTR_NONNULL(1)
NUT_ATTR_ACCESS(read_only, 1)
static inline bool nut_Bitarray_get(const uint8_t *buf, uint64_t i){
    return buf[i/8] & (UINT8_C(1) << (i%8));
}
 
NUT_ATTR_NONNULL(1)
NUT_ATTR_ACCESS(read_write, 1)
static inline void nut_Bitarray_set(uint8_t *buf, uint64_t i, bool v){
    if(v){
        buf[i/8] |= 1ull << (i%8);
    }else{
        buf[i/8] &= ~(UINT8_C(1) << (i%8));
    }
}
 
NUT_ATTR_PURE
NUT_ATTR_NONNULL(1)
NUT_ATTR_ACCESS(read_only, 1)
static inline uint8_t nut_Bitfield2_arr_get(const uint8_t *buf, uint64_t i){
    return (buf[i/4] >> (i%4*2)) & 3;
}
 
bool nut_u64_make_factorial_tbl(uint64_t k, uint64_t modulus, uint64_t bits, uint64_t max_denom, uint64_t factorials[static bits + k], uint64_t inv_factorials[static max_denom + 1]);
 
[[deprecated("Replace with nut_sieve_smallest_factors_wheel6")]]
NUT_ATTR_NONNULL(2)
NUT_ATTR_MALLOC
NUT_ATTR_ACCESS(write_only, 2)
void *nut_sieve_factorizations(uint64_t max, uint64_t *_w);
 
NUT_ATTR_CONST
uint64_t nut_get_factorizations_pitch(uint64_t w);
 
[[deprecated("Replace with nut_sieve_smallest_factors_wheel6")]]
NUT_ATTR_NONNULL(2)
NUT_ATTR_MALLOC
NUT_ATTR_ACCESS(write_only, 2)
void *nut_sieve_factors(uint64_t max, uint64_t *_w);
 
NUT_ATTR_MALLOC
uint8_t *nut_sieve_omega(uint64_t max);
 
[[deprecated("Replace with nut_sieve_smallest_factors_wheel6")]]
NUT_ATTR_MALLOC
uint64_t *nut_sieve_largest_factors(uint64_t max);
 
[[deprecated("Replace with nut_fill_factors_from_smallest_wheel6")]]
NUT_ATTR_NONNULL(1, 3)
NUT_ATTR_ACCESS(read_write, 1)
NUT_ATTR_ACCESS(read_only, 3)
void nut_fill_factors_from_largest(nut_Factors *restrict out, uint64_t n, const uint64_t largest_factors[restrict static n + 1]);
 
[[deprecated("Replace with nut_sieve_smallest_factors_wheel6")]]
NUT_ATTR_MALLOC
uint32_t *nut_sieve_smallest_factors(uint64_t max);
 
[[deprecated("Replace with nut_fill_factors_from_smallest_wheel6")]]
NUT_ATTR_NONNULL(1, 3)
NUT_ATTR_ACCESS(read_write, 1)
NUT_ATTR_ACCESS(read_only, 3)
void nut_fill_factors_from_smallest(nut_Factors *restrict out, uint64_t n, const uint32_t smallest_factors[restrict static n + 1]);
 
NUT_ATTR_MALLOC
uint32_t *nut_sieve_smallest_factors_wheel6(uint64_t max);
 
NUT_ATTR_NONNULL(1, 3)
NUT_ATTR_ACCESS(read_write, 1)
NUT_ATTR_ACCESS(read_only, 3)
void nut_fill_factors_from_smallest_wheel6(nut_Factors *restrict out, uint64_t n, const uint32_t smallest_factors[restrict static n/3 + 1]);
 
NUT_ATTR_CONST
uint64_t nut_get_factors_pitch(uint64_t w);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_sigma_0(uint64_t max);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_sigma_1(uint64_t max);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_sigma_e(uint64_t max, uint64_t e);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_dk(uint64_t max, uint64_t k, uint64_t modulus);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_phi(uint64_t max);
 
NUT_ATTR_MALLOC
uint64_t *nut_sieve_carmichael(uint64_t max);
 
NUT_ATTR_MALLOC
uint8_t *nut_sieve_mobius(uint64_t max);
 
NUT_ATTR_MALLOC
NUT_ATTR_NONNULL(2)
NUT_ATTR_ACCESS(read_only, 2)
int64_t *nut_compute_mertens_range(uint64_t max, const uint8_t mobius[static max/4 + 1]);
 
NUT_ATTR_MALLOC
uint8_t *nut_sieve_is_composite(uint64_t max);
 
NUT_ATTR_PURE
NUT_ATTR_NONNULL(2)
NUT_ATTR_ACCESS(read_only, 2)
bool nut_is_composite(uint64_t n, const uint8_t buf[static n/30 + 1]);
 
NUT_ATTR_NONNULL(2)
NUT_ATTR_MALLOC
NUT_ATTR_ACCESS(read_only, 2)
uint64_t *nut_compute_pi_range(uint64_t max, const uint8_t buf[static max/30 + 1]);
 
NUT_ATTR_PURE
NUT_ATTR_NONNULL(2, 3)
NUT_ATTR_ACCESS(read_only, 2)
NUT_ATTR_ACCESS(read_only, 3)
NUT_ATTR_NO_SAN("vla-bound")
uint64_t nut_compute_pi_from_tables(uint64_t n, const uint64_t pi_table[restrict static n/30], const uint8_t buf[restrict static n/30 + 1]);
 
NUT_ATTR_MALLOC
NUT_ATTR_NONNULL(2)
NUT_ATTR_ACCESS(write_only, 2)
uint64_t *nut_sieve_primes(uint64_t max, uint64_t *_num_primes);