Números Primos Rápidos em C

Programação C e C++
,
#1

Olá, gostaria de saber como deixar o algoritmo abaixo mais rápido. Pesquisando vi que uma boa solução seria só calcular os divisores que vão até a raiz quadrada do número, no entanto não consigo implementar isso, alguém pode me ajudar?

include < stdio.h >

int primo(int x){
int i,c = 1;

for(i = 2; i <= x - 1; i++){
    if((i % 2 == 1) || i == 2){

        if(x % i == 0){
            c++;
        }

        if(c > 2)break;
    }
}

if(c + 1 == 2){
    return 1;
}else{
    return 0;
}

}

int main(void){
int t,v;

scanf("%d",&t);

while(t--){
    scanf("%d",&v);

    if(primo(v)){
        printf("Prime\n");
    }else{
        printf("Not Prime\n");
    }
}

}

#3

#include < iostream >
#include < cmath >

using namespace std;

int main ()
{
int N, X;
cin >> N;
for(int i = 0; i < N; i++){
cin >> X;
if (X == 1){
cout << “Not Prime” << endl;
continue;
}
int cont = 0, fim = sqrt(X);
for(int j = 2; j <= fim; j++){
if (X%j == 0){
cont++;
break;
}
}
if(cont == 0) cout << “Prime” << endl;
else cout << “Not Prime” << endl;
}
return 0;
}

legenda: ‘n’ == quantos numeros
’x’ == numero da vez
Linguagem c++

1 curtida
#4

Muito obrigado amigo, consegui resolver aqui