1/*
2 * math_util_complex.hpp
3 *
4 * Created on: Oct 1, 2017
5 * Author: i-bird
6 */
7
8#ifndef OPENFPM_DATA_SRC_UTIL_MATH_UTIL_COMPLEX_HPP_
9#define OPENFPM_DATA_SRC_UTIL_MATH_UTIL_COMPLEX_HPP_
10
11//! extern vector for getFactorization
12extern std::vector<int> sieve_spf;
13
14namespace openfpm
15{
16 namespace math
17 {
18
19 #define SIEVE_MAXN 4096
20
21 /*! \brief Precompute SPF (Smallest Prime Factor) for every
22 * number till MAXN.
23 * Time Complexity : O(nloglogn)
24 *
25 */
26 void inline init_getFactorization()
27 {
28 sieve_spf.resize(SIEVE_MAXN);
29
30 sieve_spf[1] = 1;
31 for (int i = 2; i < SIEVE_MAXN; i++)
32 {
33 // marking smallest prime factor for every
34 // number to be itself.
35 sieve_spf[i] = i;
36 }
37
38 // separately marking spf for every even
39 // number as 2
40 for (int i = 4; i < SIEVE_MAXN; i += 2)
41 {sieve_spf[i] = 2;}
42
43 for (int i = 3; i*i < SIEVE_MAXN; i++)
44 {
45 // checking if i is prime
46 if (sieve_spf[i] == i)
47 {
48 // marking SPF for all numbers divisible by i
49 for (int j=i*i; j < SIEVE_MAXN; j+=i)
50 {
51 // marking spf[j] if it is not
52 // previously marked
53 if (sieve_spf[j] == j)
54 {sieve_spf[j] = i;}
55 }
56 }
57 }
58 }
59
60 /*! \brief A O(log n) function returning prime factorization
61 * by dividing by smallest prime factor at every step
62 *
63 * \param x number to factor
64 * \param factorization output
65 *
66 */
67 inline void getFactorization(int x, std::vector<size_t> & ret)
68 {
69 ret.clear();
70 while (x != 1)
71 {
72 ret.push_back(sieve_spf[x]);
73 x = x / sieve_spf[x];
74 }
75 }
76
77 }
78}
79
80
81#endif /* OPENFPM_DATA_SRC_UTIL_MATH_UTIL_COMPLEX_HPP_ */
82