GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Números Primos Rápidos em C

code
programação
Tags: #<Tag:0x00007ff78cd67c58> #<Tag:0x00007ff78cd67b18>

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


#4

Muito obrigado amigo, consegui resolver aqui