Gain insights into competitive programming, explore C++ skills with theory, code samples, practice problems, and master faster implementation for contests like ACM ICPC, Google CodeJam, and HackerCup.

Competitive programming can be a great way to build out your programming skills, get on any major company’s radar, and earn a little extra cash along the way.

In this course, you will learn to prepare for competitive programming contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more.

Each topic is broken down with a healthy mix of theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation.

You will need some solid C++ foundations coming into this course, but by the end it, you will be confident enough in your C++ skills to take home the win.

Competitive Programming in C++: The Keys to Success

## Problem statement
Given two integers, $N$ and $M$, print all primes between $N$ and $M$ (*both inclusive*).

**Input format**

The only line of input contains two integers $N$ and $M$ $(1 \leq N \leq M \leq 10^9)( M-N \leq 10^6)$.

---

## Sample
**Input**
```
100000000 100000100
```

**Output**
```
100000007 100000037 100000039 100000049 100000073 100000081
```

---

## Sieve
Obviously, Sieve of Eratosthenes comes to mind. Now, two things don't work right here:

1. $M <= 10^9$, we don't have enough memory to declare an array of a billion integers (4 GB memory).
2. Even if we could declare an array that big, the time complexity would be $O(M*log(logM))$, which is obviously very slow.

**Observation**: $M - N <= 10^6$

---

## Segmented sieve
Since the range in which we want the generate the primes is at max $10^6$, we can run a modified version of sieve on a Boolean array $A[]$ of size $M-N+1$ such that.

* $A[0]$ - denotes whether $N$ is prime or not.
* $A[1]$ - denotes whether $N+1$ is prime or not.
* ...
* $A[M-N]$ - denotes whether $M$ is prime or not.

---

## Marking multiples not-prime
Comparing to sieve where we iterate up to $\sqrt{N}$ and if the current number is prime, we mark its multiples not-prime.

Here, we will iterate up to $\sqrt{M}$, but if the number doesn't belong in the range $[N, M]$, we don't know if it's a prime or not. So, in this case, we will mark multiples not-prime for **all** the numbers in $[2, \sqrt(M)]$.

We only need to mark the multiples if the multiple is between $N$ and $M$. To do this, we start with the first multiple of this number that is greater than or equal to $N$.

First multiplex of $x$ just greater than or equal to $N$ can be calculated as follow:

$m = (\lfloor\frac{N-1}{x}\rfloor + 1) * x$ 

# Problem statement
Given two integers, $N$ and $M$, print all primes between $N$ and $M$ (*both inclusive*).

**Input format**

The only line of input contains two integers $N$ and $M$ $(1 \leq N \leq M \leq 10^9)( M-N \leq 10^6)$.

---

# Sample
**Input**
```
100000000 100000100
```

**Output**
```
100000007 100000037 100000039 100000049 100000073 100000081
```

---

# Sieve
Obviously, Sieve of Eratosthenes comes to mind. Now, two things don't work right here:

1. $M <= 10^9$, we don't have enough memory to declare an array of a billion integers (4 GB memory).
2. Even if we could declare an array that big, the time complexity would be $O(M*log(logM))$, which is obviously very slow.

**Observation**: $M - N <= 10^6$

---

# Segmented sieve
Since the range in which we want the generate the primes is at max $10^6$, we can run a modified version of sieve on a Boolean array $A[]$ of size $M-N+1$ such that.

* $A[0]$ - denotes whether $N$ is prime or not.
* $A[1]$ - denotes whether $N+1$ is prime or not.
* ...
* $A[M-N]$ - denotes whether $M$ is prime or not.

---

# Marking multiples not-prime
Comparing to sieve where we iterate up to $\sqrt{N}$ and if the current number is prime, we mark its multiples not-prime.

Here, we will iterate up to $\sqrt{M}$, but if the number doesn't belong in the range $[N, M]$, we don't know if it's a prime or not. So, in this case, we will mark multiples not-prime for **all** the numbers in $[2, \sqrt(M)]$.

We only need to mark the multiples if the multiple is between $N$ and $M$. To do this, we start with the first multiple of this number that is greater than or equal to $N$.

First multiplex of $x$ just greater than or equal to $N$ can be calculated as follow:

$m = (\lfloor\frac{N-1}{x}\rfloor + 1) * x$ 

In this lesson, we'll discuss how to implement the segmented Sieve: a very popular variation of sieve.


Introduction

Complexity Analysis

Number Theory

Arrays and Vectors

Sieve of Eratosthenes

Strings

Sorting

Linked List

Stack

Queue

Binary Tree

2 Pointers

Heap

Binary Search Tree

Balanced Binary Search Tree

Course Conclusion

Solved Problem - Segmented Sieve

Problem statement

Sample

Sieve

Segmented sieve