URI - 1221 - Primo Rápido - Matemática - C++

Plataforma: URI
Problema: 1221

Enunciado:
Mariazinha sabe que um Número Primo é aquele que pode ser dividido somente por 1 (um) e por ele mesmo. Por exemplo, o número 7 é primo, pois pode ser dividido apenas pelo número 1 e pelo número 7 sem que haja resto. Então ela pediu para você fazer um programa que aceite diversos valores e diga se cada um destes valores é primo ou não. Acontece que a paciência não é uma das virtudes de Mariazinha, portanto ela quer que a execução de todos os casos de teste que ela selecionar (instâncias) aconteçam no tempo máximo de um segundo, pois ela odeia esperar.

Linguagem: C++

Solução:

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    
    int n, x, primo;
    
    cin >> n;
    
    while (n--) {
        
        cin >> x;
        
        int contador = 3;
        
        if (x % 2 == 0 && x > 2)
            primo = 0;
        
        else
            primo = 1;
        
        while (contador <= (int) sqrt(x)) {
            
            if (x % contador == 0) {
                primo = 0;
                break;
            }
            
            contador += 2;
            
        }
        
        if (primo == 0 || x == 1)
            cout << "Not Prime" << endl;
        else
            cout << "Prime" << endl;
        
    }
    
    return 0;
}