Isprime(素数判定) (math/isprime.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-03-24 18:33:34+09:00

なにこれ

素数判定を行う．

関数

• isprime(n)：n が素数であれば true を，そうでなければ false を返す．

計算量

• isprime(n)：$O(\sqrt n)$

---

Verified with

• test/aoj_ALDS1_1_C_isprime.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

bool isprime(long long n) {
	if(n == 2 || n == 3 || n == 5) return true;
	if(n < 2 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;

	long long i = 7;
	while(i * i <= n) {
		for(int k : {4, 2, 4, 2, 4, 6, 2, 6}) {
			if(i * i > n) break;
			if(n % i == 0) return false;
			i += k;
		}
	}

	return true;
}

#line 2 "math/isprime.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

bool isprime(long long n) {
	if(n == 2 || n == 3 || n == 5) return true;
	if(n < 2 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;

	long long i = 7;
	while(i * i <= n) {
		for(int k : {4, 2, 4, 2, 4, 6, 2, 6}) {
			if(i * i > n) break;
			if(n % i == 0) return false;
			i += k;
		}
	}

	return true;
}

Back to top page