Is Prime(素数判定)
(math/number-theory/is-prime.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "math/number-theory/is-prime.hpp"

is_prime

bool is_prime(int64_t x)

$x$ が素数なら true、素数でなければ false を返します。

制約

• $0 \le x$

計算量

• $O(\sqrt x)$

Verified with

• test/verify/aoj-alds-1-1-c.test.cpp

Code

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

#line 1 "math/number-theory/is-prime.hpp"
bool is_prime(int64_t x) {
  for(int64_t i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}

Back to top page