Números Primos Rápidos em C

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");
    }
}

}

2 Respostas

Solucao aceita

Will_Spader 11 de out. de 2017 1 like

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

Rafael_Vasconcelos 11 de out. de 2017

Muito obrigado amigo, consegui resolver aqui

2 Respostas

Topicos relacionados