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 <stdio.h>
#include <math.h>

int main() {
    
    int n, x, primo;
    
    scanf("%i", &n);
    
    while (n--) {
        
        scanf("%i", &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)
            printf("Not Prime\n");
        else
            printf("Prime\n");
        
    }
    
    return 0;
}