Jump to content

Primos and returns question


Flames
 Share

Recommended Posts

#include <stdio.h>

int primo(int n){
   int i;

   for(i=2; i <= n;i++){
       if (n % i == 0)
          return 0;
   }
   return 1;
}

int main (void){
    int i;
    for(i=1;i<=25;i++){
        printf("o numero %i %s\n",i,((primo(i)? "primo": "not primo" )));
    }
    return 0;

}

A parte do codigo no main o printf <--- fui buscar na internet à sorte porque a funcao primo já a tinha aqui comigo a minha questao é segundo esse if ele vai "buscar" o return 0 e diz que não é primo ou o return 1 e diz que é primo...

Só que não percebo como faz exactamente ja tentei procurar na internet Printf's e returns e não consigo achar a ligacao.

O meu objectivo era só fazer printf quando fosse return 1 (espero que esta explicação não esteja numa salada russa).

Eu sei que podia fazer printf dentro da funcao blabla... mas o exercicio requer apenas return 0 e return 1 logo ded uzo que isto tenha uma forma de ser correcta...

Desculpem mais uma vez o incómodo :S

Link to comment
Share on other sites

Em 1º lugar o que tens é uma atribuição condicional, ou seja se primo(i) for verdadeiro, fica com o valor "primo" senão fica com "not primo" que por sua vez é impresso no printf no lugar do %s.

Se apenas queres imprimir os primos, mete algo como:

if(primo(i)) printf("o numero %d e primo\n", i);

Em 2º lugar, não me quer parecer que essa função esteja correcta para valores superiores a 1, pois a ultima iteração do ciclo é quando vê o resto entre um numero e si proprio logo retornará sempre 0. Tira o i<=n e põe apenas i<n ...

Link to comment
Share on other sites

Em 1º lugar o que tens é uma atribuição condicional, ou seja se primo(i) for verdadeiro, fica com o valor "primo" senão fica com "not primo" que por sua vez é impresso no printf no lugar do %s.

Se apenas queres imprimir os primos, mete algo como:

if(primo(i)) printf("o numero %d e primo\n", i);

Em 2º lugar, não me quer parecer que essa função esteja correcta para valores superiores a 1, pois a ultima iteração do ciclo é quando vê o resto entre um numero e si proprio logo retornará sempre 0. Tira o i<=n e põe apenas i<n ...

Estive agora a pensar o return 0, Se calhar o que vou dizer é uma grande mentira, funciona como falso e o return 1 como verdadeiro...  Sim o i<= é sem = 🙂

Link to comment
Share on other sites

Só precisas de verificar ate a raiz quadrada do número.

Sim, até ao inteiro inferior ou igual à raíz quadrada. E podes saltar os números pares, visto que o teu algoritmo já valida o 2 automaticamente. Só tens que fazer essa verificação antes.

Existe um ainda mais eficiente, que é saltando de 6 em 6, se aprovares o 3 também automaticamente, apenas validando o valor anterior e o seguinte.

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

Olá.

Como estou a aprender C, aproveitei e fiz tb um programa que fizesse o mesmo mas estou com alguns problemas que devem ser de precisão.

O código é o seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int ePrimo(int x);
int ePrimo2(int x);
void imprimeResultado(int resultado, int numero, time_t time1, time_t time2);

int main()
{
    double dif_sec;
    int escolha, numero, resultado, inferior, superior,i;
    time_t time1,time2;

   do{

        printf("Escolha uma das seguintes opcoes:\n");
        printf("[1] Calcular se numero e primo.\n");
        printf("[2] Calcular se numero e primo (raiz).\n");
        printf("[3] Listar primos entre dois numeros.\n\n");
        scanf("%d", &escolha);

    } while (escolha < 1 || escolha > 3);

    switch (escolha)
    {
        case 1:
            printf("Qual o numero que quer confirmar se e primo?\n");
            scanf("%d", &numero);
            time (&time1);
            resultado = ePrimo(numero);
            time (&time2);
            imprimeResultado(resultado, numero, time1, time2);
            break;
        case 2:
            printf("Qual o numero que quer confirmar se e primo?\n");
            scanf("%d", &numero);
            time (&time1);
            resultado = ePrimo2(numero);
            time (&time2);
            imprimeResultado(resultado, numero, time1, time2);
            break;
        case 3:
            printf("Insira o limite inferior\n");
            scanf("%d", &inferior);
            printf("Insira o limite superior\n");
            scanf("%d", &superior);

            if (inferior % 2 == 0){
                inferior +=1;
            }

            for (i = inferior; i <= superior; i+=2){
                time (&time1);
                resultado = ePrimo(i);
                time (&time2);
                imprimeResultado(resultado, i, time1, time2);
            }
            break;
    }
    return 0;
}

int ePrimo2(int numero){
    int i,resultado;
    int numeroFinal = sqrt(numero)+1;
    for (i = 2; i <= numeroFinal; i++){
        resultado = ePrimo(i);
        if (resultado == 1){
            if ( numero%i==0){
                return 0;
            }
        }
    }
    return 1;
}

int ePrimo(int numero){
    int i;
    for (i = 2; i < numero; i++){
        if ( numero%i == 0){
            return 0;
        }
    }
    return 1;
}

void imprimeResultado(int resultado, int numero, time_t time1, time_t time2){
    double dif_sec;
    dif_sec = difftime (time2,time1);
    if (resultado == 0){
        printf("O numero %d nao e primo\n", numero);
    }
    else{
        printf("O numero %d e primo\n", numero);
    }
    printf("Demorou %.2f segundos a calcular se o numero era primo\n", dif_sec);
}

Pelo que vi, o código está a funcionar direito e apesar de achar que a forma como estou a verificar o tempo de execução do algoritmo não é o melhor, o método da raiz é claramente mais eficiente.

Agora as minhas dúvidas que não sei se derivam da minha máquina, isto é, de Win 7 64 bits.

Se com o código, inserir o número 1010189899 (que tem dez dígitos) tanto nos dois métodos, ele calcula e diz que o número é primo. Se o número for de 11 dígitos, como o 10240297597, ele não consegue calcular. Aliás, coloquei no printf o numero para verificar se o número que entra é o mesmo que sai. A partir de 11 dígitos não é, isto é, insiro  10240297597 e no último print, ele imprime um número qualquer.

Alguém me sabe explicar porquê?

kodiak

Link to comment
Share on other sites

Não tem de ser double, a funcao tem de ficar com um long long, visto que não precisas de casas décimais:

int ePrimo2(long long numero){
    long long i,resultado;
    long long numeroFinal = sqrt(numero)+1;
    for (i = 2; i <= numeroFinal; i++){
        resultado = ePrimo(i); //Hum? Ve o que esta escrito a seguir
        if (resultado == 1){
            if ( numero%i==0){
                return 0;
            }
        }
    }
    return 1;
}

Para alem disso, na funcao ePrimo2 estás a chamar ePrimo, sem guardares os valores, assim, para calculares qualquer primo com ePrimo2 tens de verificar antes com ePrimo se todos os primos até sqrt(N) sao primos, o que é uma perda de tempo.

Tens duas solucoes relativamente faceis:

No inicio do programa calculas todos os primos até um dado valor MAX, numa array prim[d] e depois só poderás calcular primos até MAX^2 (O que é em principio o algoritmo mais rápido), e depois fazes:

long long MAX=<numero até onde calculaste os primos>;
long long primos[]={2,3,5,7,....};
long long d=<numero de primos>
int ePrimo2(long long numero){
    long long i,resultado;
    long long numeroFinal = sqrt(numero)+1;
    for (i = 0; primos[i] <= numeroFinal; i++){
            if ( numero%primos[i]==0){
                return 0;
            }
    }
    return 1;
}

A outra solucao mais lenta, mas mais facil de implementar é só alterares uma parte do teu código:

int ePrimo2(long long numero){
    long long i,resultado;
    long long numeroFinal = sqrt(numero)+1;
    for (i = 2; i <= numeroFinal; i++){
        if ( numero%i==0){
                return 0;
        }
    }
    return 1;
}

<Signature goes here>

Link to comment
Share on other sites

Não tem de ser double, a funcao tem de ficar com um long long, visto que não precisas de casas décimais:

Viva.

Obrigado pela resposta. Nem sabia que existia esse tipo 😄

Mas estou com uma dúvida.

eu acho que dentro da função ePrimo2 tem de haver a chamada à ePrimo isto porque os métodos da raiz é:

Achar o numero inteiro superior à raiz;

Calcular os primos existentes até ao número anterior;

e finalmente verificar se algum desses números primos é divisor.

Pelo menos foi com essa ideia que eu fiquei...

Link to comment
Share on other sites

Sim, esse método funciona, eu não disse o contrário, mas demora mais tempo do que se apenas verificares se todos os números até á raiz] são divisores do numero. Vê o segundo código que enviei.

Se quiseres efetivamente verificar se os números são primos, tal como tu disseste, mais vale primeiro préprocessares quais são os números primos. Com por exemplo o crivo de erastotenes ou de atkin. Podes encontrar uma visualização do crivo de erastótenes aqui: https://wiki.portugal-a-programar.pt/algoritmo:crivo_de_eratosthenes

<Signature goes here>

Link to comment
Share on other sites

Repara que para utilizares o crivo de erathostenes que está na wiki para calcular valores de 11 dígitos, também precisas de ter 11 dígitos de memória RAM (ou seja, mais de 10GB livres). Caso contrário vais demorar mesmo muito tempo para que o computador possa fazer a troca de dados de/para disco. Para além disso, devido a estares permanentemente a ir buscar ou a alterar valores desde o início (até sqrt(n)) até ao final do array, o disco vai estar permanentemente a fazer swap (não há caching possível).

Uma solução para isto é utilizares um crivo que remove os múltiplos de 2 e de 3, que baixa a utilização de memória para 1/3:

    // N - max sieve value
   long sqrtN = sqrt(N);
   long x = N/3;
   bool *notPrimes = calloc(x, sizeof(bool)); // zero init
   long i = 5, a = 2, b, j;

   for (; i < sqrtN; i += a, a = 6 - a) {
       if (!notPrimes[i/3]) {
           for (j = i*i, b = a; j < N; j += b*i, b = 6 - b) {
               notPrimes[j/3] = 1; // not prime
           }
       }
   }

// validação
if ((A % 2) && (A % 3) && !notPrime[A/3]) { println("É primo"); }

Mas, mesmo assim precisas de mais de 3GB livres para conseguires calcular todos os números primos até 10.000.000.000.

Em vez de utilizares um array de chars/bools para registares os números primos, podes trabalhar com operações bitwise para trabalhares com um array de bits:

    // N - max sieve value
   long sqrtN = sqrt(N);
   long x = N/3;
   //bool *notPrimes = calloc(x, sizeof(bool));
   int lsize = sizeof(int) * 8;
   int *notPrimes = calloc(x/lsize + 1, sizeof(int));
   long i = 5, a = 2, b, j;

   for (; i < sqrtN; i += a, a = 6 - a) {
       long s = i / 3;
       int intPos = s / lsize;
       int bitPos = s % lsize;
       if (!(notPrimes[intPos] & (1 << bitPos))) {
           for (j = i*i, b = a; j < N; j += b*i, b = 6 - b) {
               long s = j / 3;
               int intPos = s / lsize;
               int bitPos = s % lsize;
               if (!(notPrimes[intPos] & (1 << bitPos)))
                   notPrimes[intPos] += (1 << bitPos);
           }
       }
   }

// validação
if ((A % 2) && (A % 3) && !(notPrime[A/3/lsize] & (1 << ((A/3) % lsize)))) { println("É primo"); }

Assim gastas 1/8 da memória do algoritmo anterior, ou 1/24 menos memória que o crivo de erathostenes original, com uma penalização na velocidade do algoritmo para máximos inferiores à quantidade de memória disponível (em bytes).

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.