# Solved Problem - Check Prime

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

## We'll cover the following

## 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.

Get hands-on with 1400+ tech skills courses.