Table of contents

• Usage
• Algorithm 1
  • Explanation
  • Time Complexity
  • Code
• Algorithm 2
  • Explanation
  • Time Complexity
  • Code

# Usage

Determine if a given number is a prime number.

# Algorithm 1

# Explanation

Every composite number X has a number p such that $p \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(\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 $\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(N \log \log N)$

For finding

$O(1)$

# 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