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

# Representation
Any integer can be represented as the product of a power of primes. For example:

* $6 = 2\times3$
* $24 = 2^3\times3$
* $3087 = 3^2\times7^3$

Breaking an integer into its prime factors with their corresponding powers is called prime factorization.

Prime factorization of an integer is a very common problem and will reoccur in a wide range of topics, hence it is important to know an efficient way to do it.


--- 

# Prime Factors
**Property**: _An integer $N$ will have at most one prime factor $\geq\sqrt{N}$_.

If an integers $n$ has $m$ prime factors $(p_1 < p_2 < ... < p_m)$. Then either,

* All prime factors are less than or equal to $\sqrt{N}$ or,
* All prime factors except $p_m$ are less than or equal to $\sqrt{N}$.

**Proof**: Using contradiction for $N$, if the above statement is not true, then there must be two prime factors, $p_1$ and $p_2$,​​ such that:

$p_1 \geq \sqrt{N},p_2 \geq \sqrt{N}$

But since $p_1 \neq p_2$, both can't be equal to $\sqrt{N}$.

In that case $p_1 \times p_2 > N$, and hence they can't be factors of $N$.

---

**Property**: _If $N$ has a prime factor $p > \sqrt{N}$. Then the power of $p$ in prime factorization of $N$ is $1$_

**Proof**: Again, by contradiction, if the power is greater than $1$, then $p \times p > N$, which is not possible.

---

In the next lesson, we'll see how to find the prime factorization of a number.


In this lesson, we'll discuss about prime factorization of 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

Prime Factors

Representation

Prime Factors