number-theory

# # 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

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


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!