Prime Numbers

Calendar Clock iconCalendar Clock icon


Table of contents

# Usage

Determine if a given number is a prime number.

# Algorithm 1

# Explanation

Every composite number X has a number p such that pXp \leq \sqrt{X}.
And a number which is not a composite number is a prime number.

0 and 1 is not prime numbers.
Even numbers except 2 are not prime numbers.

# Time Complexity

O(n=0xn)O(\displaystyle\sum_{n=0}^x \sqrt{n})

# Code

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
bool isPrime(Int x) {
  if (x == 1) return false;
  if (x == 2) return true;
  if (x % 2 == 0) return false;
  Int sqrtX = Int(sqrt(x));
  for (Int n = 3; n <= sqrtX; n += 2)  if (x % n == 0) return false;
  return true;

# Algorithm 2

The Sieve of Eratosthenes

# Explanation

Let the max number of input X.
(This algorithm requires X+1 memory.)

  • Initialize vector<bool> isPrime whose length is X+1 with elements true.
  • Set 0th and 1st elements to false
  • Compute sqrtX X\sqrt{X}.
  • Execute the following from n = 2 to sqrtX
  • If isPrime[n] is true, let the number as it is and set all its multiples ot false.

# Time Complexity

For building a table

O(NloglogN)O(N \log \log N)

For finding


# Code

#define MAX_X 100000001
vector<bool> isPrime(MAX_X, true);

void eratosthenes(vector<bool> &isPrime) {
  Int x = isPrime.size()-1;
  Int x_sqrt = int(sqrt(x));
  isPrime[0] = isPrime[1] = false;
  loop(i,2,x_sqrt+1) {
    if (isPrime[i]) {
      for(Int j = i*2; j <= x; j += i) {
        isPrime[j] = false;

isPrime[31]; // -> true

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!