Primality Test

In this lesson, we'll learn how to check whether a number is prime or not.

First, let's recall what a prime number is. A number is a prime if and only if it has exactly positive divisors. For example, and are prime numbers, while isn't since it has other divisors than and like . If a number has more than positive divisors, we call it composite.

Given this definition of prime numbers, there is a simple question we can ask ourselves: how to check if a number is prime?

The naive idea is to iterate over all numbers in the range and check if is a divisor of . To do it, we need to check if . If we can find such , it means that is not a prime. Otherwise, it's a prime number.

The complexity of this algorithm is .

#include <iostream>
using namespace std;

int main()
{
	int p;
	cin >> p;

	bool isPrime = true;