整数問題解法

このnoteは、AtCoder 版！マスター・オブ・整数 (素因数分解編)を読んでコード部分を抜き出したりしてまとめたもので、自分の勉強のためのみに書いたものです。
書き間違いなどあるかもしれませんが読む場合には自己責任でお願いします。

・素数判定

C++

bool is_prime(long long N) {
  if (N == 1) return false;
  for (long long i = 2; i * i <= N; i++) {
    if (N % i == 0) return false;
  }
  return true;
}

Python

def is_prime(N):
  if N == 1: return False
  i = 2
  while i * i <= N:
    if N % i == 0: return False
    i += 1
  return True

・約数列挙

(vector勉強用リンク)

C++

# include <vector>
# include <algorithm>

vector<long long> enum_divisors(long long N) {
  vector<long long> res;
  for (long long i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      res.push_back(i);
      if (N/i != i) res.push_back(N/i);
    }
  }
  sort(res.begin(), res.end());
  return res;
}

vector初期化パターン

変数名、変数名(要素数)、変数名(要素数、初期値)

Python

def enum_divisors(N):
  res = []
  i = 1
  while i * i <= N:
    if N % i == 0:
      res.append(i)
      if N // i != i:
        res.append(N // i)
    i += 1
  res.sort()
  return res

・素因数分解

C++

#include<vector>
using pll = pair<long long, long long>;

vector<pll> prime_factorize(long long N) {
  vector<pll> res;
  for (long long a = 2; a * a <= N; a++) {
    if (N % a != 0) continue;
    long long ex = 0; //指数
    while (N % a == 0) {
      ex++;
      N /= a;
    }
    res.push_back({a,ex});
  }
  if (N != 1) res.push_back({N, 1});
  return res;
}

pair<>の各要素へのアクセスは、res[i].first と res[i].second

Python

def prime_factorize(N):
  res = []
  a = 2
  while a * a <= N:
    if N % a != 0:
      a += 1
      continue
    ex = 0
    while N % a == 0:
      ex += 1
      N = N // a
    res.append((a,ex))
    a += 1
  if N != 1:
    res.append((N,1))
  return res

・ついでにメモ(途中終了)

void pr(long long x){ cout << x << endl; exit(0); }