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 a number, $N$, check if it’s prime or not. Do this for $T$ test cases.

**Input format**

The first line contains a positive integer $T$ $(1 \leq T \leq 10^3)$.

The following $T$ lines contain a positive integer $N$ $(2 \leq N \leq 10^8)$.

**Output format**
For each integer, $N$, print `yes` if $N$ is prime, otherwise print `no` on a new line.


--- 

## Sample
**Input**
```
5
34 
29 
11 
14 
6
```

**Output**
```
no 
yes 
yes 
no 
no
```

---


## Brute force
The brute force solution would be to check whether N has any factor between $2$ and $N-1$ (*inclusive*).

The time complexity would be $O(N)$ for one test case. So the overall time complexity would be $O(T*N)$.

---

## Optimization
Similar to the factorization problem. We only need to iterate up to $\sqrt{N}$ to find factors.

This reduces our time complexity to $O(T*\sqrt{N})$, which is good enough for given the constraints.



# Problem statement

Given a number, $N$, check if it’s prime or not. Do this for $T$ test cases.

**Input format**

The first line contains a positive integer $T$ $(1 \leq T \leq 10^3)$.

The following $T$ lines contain a positive integer $N$ $(2 \leq N \leq 10^8)$.

**Output format**
For each integer, $N$, print `yes` if $N$ is prime, otherwise print `no` on a new line.


--- 

# Sample
**Input**
```
5
34 
29 
11 
14 
6
```

**Output**
```
no 
yes 
yes 
no 
no
```

---


# Brute force
The brute force solution would be to check whether N has any factor between $2$ and $N-1$ (*inclusive*).

The time complexity would be $O(N)$ for one test case. So the overall time complexity would be $O(T*N)$.

---

# Optimization
Similar to the factorization problem. We only need to iterate up to $\sqrt{N}$ to find factors.

This reduces our time complexity to $O(T*\sqrt{N})$, which is good enough for given the constraints.



In this lesson, we'll look at an efficient way to perform the primality test.


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 - Check Prime

Problem statement