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

# Generating primes
Given an integer $N$, you are asked to print all the prime numbers between $1$ and $N$.

Using what we have discussed so far, one way to do this would be to iterate over all the numbers from  $1$ to $N$ and check if it's prime or not.

Time Complexity - $O(N*\sqrt{N}).$

It should be okay for $N$ up to $10^4$ or even $10^5$ but not more.

---

# Sieve of Eratosthenes
The Sieve of Eratosthenes is a simple algorithm to generate all primes from $1$ to $N$ in $O(N*log(logN))$.

Steps:

1. Create a list of all numbers from $2$ to $N$. Initially, all numbers are unmarked.
 
2. Starting from $p=2$, we will mark all multiples of $2$ less than or equal to $N$. These numbers are definitely not prime since $2$ divides them.

3. Move to the next unmarked number, i.e., $p = 3$. Mark all its multiples.


4. Stop if $p>\sqrt{N}$

Each unmarked number that we visit is a prime because all non-primes will be marked by one of its factors before we reach this number.

We can use a Boolean array of size $N$ to distinguish between marked and unmarked numbers.

Let's understand the process better using the illustration below for $N = 30$. We will stop after we reach $ceil(\sqrt30)$ i.e $6$

In this lesson, we'll see an efficient algorithm to generate prime numbers.

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

Sieve of Eratosthenes

Generating primes