# IsPrime | School Method

Given a positive integer, check if the number is prime or not. A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples of first few prime numbers are {2, 3, 5, \
**Examples :** \
 

```
Input:  n = 11
Output: true

Input:  n = 15
Output: false

Input:  n = 1
Output: false
```

 

**School Method** \
A simple solution is to iterate through all numbers from 2 to n-1 and for every number check if it divides n. If we find any number that divides, we return false. <br>

```
// A school method based C++ program to check if a
// number is prime
#include <bits/stdc++.h>
using namespace std; 
bool isPrime(int n)
{    
// Corner case    
if (n <= 1)  
return false;     
// Check from 2 to n-1    
for (int i=2; i<n; i++)        
if (n%i == 0)            
return false;     
return true;} 
// Driver Program to test above function
int main()
{    
isPrime(11)? cout << " true\n": cout << " false\n";
isPrime(15)?  cout << " true\n": cout << " false\n";
return 0;
}
    
```

**Output :** \
&#x20;

```
true
false
```

Time complexity of this solution is O(n)<br>

**Optimized School Method** \
Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of smaller factor that has been already checked.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soveet-nayak.gitbook.io/algorithms/number-theory/isprime-or-school-method.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.