make primelist

ソースコード

 1const int MAX = 31624;  // 必要な最大数の平方根
 2int is_prime[MAX];
 3vector<int> primelist;
 4
 5void make_primelist() {
 6  for (int i = 2; i < MAX; ++i) {
 7    is_prime[i] = 1;
 8  }
 9  for (int i = 2; i*i <= MAX; ++i) {
10    if (!is_prime[i]) continue;
11    for (int j = i+i; j <= MAX; j += i) {
12      is_prime[j] = 0;
13    }
14  }
15  for (int i = 2; i < MAX; ++i) {
16    if (is_prime[i]) {
17      primelist.emplace_back(i);
18    }
19  }
20  return;
21}
22
23vector<int> factorization(int n) {
24  vector<int> res;
25  for (const int &p : primelist) {
26    if (p * p > n) break;
27    if (n % p == 0) {
28      n /= p;
29      while (n % p == 0) {
30        n /= p;
31      }
32      res.emplace_back(p);
33    }
34  }
35  if (n != 1) {
36    res.emplace_back(n);
37  }
38  return res;
39}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/math/make_primelist.cpp