• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

black

Número é primo ou não..

13 mensagens neste tópico

tenho que realizar um programne que lei um número do utilizadore diz se esse número é primo ou não..

alguem me pode ajudar??

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Basicamente tens de verificar quantos divisores tem o número introduzido.

pseudocodigo

inicio

ler numero

para i desde numero até 1 incremento -1

inicio

se numero mod i = 0 então qtd <- qtd + 1

fim

se qtd = 2 então escreve 'Número primo'

se não escreve 'Não é número primo'

fim

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um número par nunca é primo.

Um número par maior que 2 nunca é primo.

Quando detectas que o número não é primo podes parar logo.

Não sei se há algum algoritmo mais eficiente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um número par nunca é primo.

Quando detectas que o número não é primo podes parar logo.

Não sei se há algum algoritmo mais eficiente.

Excepto o 2.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pseudocodigo

inicio

  ler numero

  para i desde numero até 1 incremento -1

      inicio

        se numero mod i = 0 então qtd <- qtd + 1

      fim

  se qtd = 2 então escreve 'Número primo'

  se não escreve 'Não é número primo'

fim

Não sei se há algum algoritmo mais eficiente.

Não é preciso começar no próprio número.

Basta começar na raiz do quadrada do número.

Também é (probabilisticamente) melhor começar pelos números pequenos e avançar até à raiz quadrada -- é melhor porque os números pequenos têem mais múltiplos.

inicio
   ler numero
   validar numero
   se numero for invalido sair com erro
   se numero for par escreve "Número primo" e sai
   para i desde 3 até (raiz quadrada de número) incremento 2
      inicio
         se numero mod i = 0 então
            inicio
               imprime "Número primo" e sai
            fim
      fim
   imprime 'Não é número primo'
fim

E ainda há mais métodos, que são "melhores" para números *enormes*: http://en.wikipedia.org/wiki/Primality_test

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não sei que métodos existem, mas não vale a pena estar a testar os restos das divisões por todos os números de não sei quanto até não sei quanto. Basta testar as divisões pelos número primos, já que os outros números todos se obtêm por multiplicações dos primos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não é preciso começar no próprio número.

Basta começar na raiz do quadrada do número.

Também é (probabilisticamente) melhor começar pelos números pequenos e avançar até à raiz quadrada -- é melhor porque os números pequenos têem mais múltiplos.

Eu dei-lhe o método mais fácil. Esse é o Crivo de Eratóstenes (ou similar) que é mais avançado, e quem não consegue chega ao método que eu falei muito menos consegue chegar ao crivo...

Eu não sei que métodos existem, mas não vale a pena estar a testar os restos das divisões por todos os números de não sei quanto até não sei quanto. Basta testar as divisões pelos número primos, já que os outros números todos se obtêm por multiplicações dos primos.

Mas para testar as divisões por números primos antes tens de os calcular não?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Por acaso agora lembro-me de há muitos anos ter feito um programa em C para calcular números primos, e era isso que fazia, ia guardando os primos num array e para saber se um novo número (só os impares, depois do 2 :)) era primo tentava a divisão por todos os elementos do array. Hei-de ver se encontro isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Encontrei... este código já tem 10 aninhos. Isto foi uma "disputa" entre mim e um colega, a ver quem calculava primos mais depressa.

#include <stdio.h>
#include <time.h>
#include <sys/times.h>
#include <stdlib.h>

#define TAM_BUFFER_PRIMOS  (500 * 1000)   /*5milhs: 349k prims  47s c/optim*/
                                          /*                   118s s/optim*/
                                          /*1milh: 78.5k prims 15.5s s/optim*/
                                          /*                    6.3s c/optim*/
                                          /*170k:  15.5k prims 1.6s s/optim*/
                                          /*                   0.6s c/optim*/

#define bool    char
#define FALSE   0
#define TRUE    -1


bool  mostra = TRUE;


/*
calc_primos_slow (int Lim)
{
   static int primos[TAM_BUFFER_PRIMOS];
   int  x, ip = 0, i;
   bool  primo;

      primos[ip++] = 1;
      primos[ip++] = 2;
      primos[ip++] = 3;
      for (x = 5; x <= Lim; x += 2)  {

          primo = TRUE;
          for (i = 2; i < ip; i++)
              if ((x % primos[i]) == 0)  {
                 primo = FALSE;
                 break;
               }
      
          if (primo)  {
             primos[ip++] = x;
             if (mostra)
                printf("%i\n", x);
           }
       }

      return ip;
}
   /**/


calc_primos (int Lim)
{
   static int primos[TAM_BUFFER_PRIMOS];
   int   x, ip = 0, i;
   bool  primo;

      primos[ip++] = 1;
      primos[ip++] = 2;
      primos[ip++] = 3;
      for (x = 5; x <= Lim; x += 2)  {

          primo = TRUE;
          for (i = 2; (i < ip) && (primos[i] <= (x / primos[i])); i++)
              if ((x % primos[i]) == 0)  {
                 primo = FALSE;
                 break;
               }

          if (primo)  {
             primos[ip++] = x;
             if (mostra)
                printf("%i\n", x);
           }
       }

      return ip;
}


calc_primos_div (int Lim)
{
   static int primos[TAM_BUFFER_PRIMOS];
   int    x, ip = 0, i;
   bool   primo;
   div_t  divres;

      primos[ip++] = 1;
      primos[ip++] = 2;
      primos[ip++] = 3;
      for (x = 5; x <= Lim; x += 2)  {

          primo = TRUE;
          for (i = 2; i < ip; i++)
              divres = div(x, primos[i]);
              if ((divres.rem == 0) || (primos[i] > divres.quot)) {
                 primo = FALSE;
                 break;
               }

          if (primo)  {
             primos[ip++] = x;
             if (mostra)
                printf("%i\n", x);
           }
       }

      return ip;
}


/*
void calc_graf (int Lim)
{
   static int primos[TAM_BUFFER_PRIMOS];
   int   x, ip = 0, i;
   bool  primo;

      primos[ip++] = 1;
      primos[ip++] = 2;
      primos[ip++] = 3;
      for (x = 5; x <= Lim; x += 2)  {

          primo = TRUE;
          for (i = 2; (i < ip) && (primos[i] <= (x / primos[i])); i++)
              if ((x % primos[i]) == 0)  {
                 primo = FALSE;
                 break;
               }

          if (primo)  {
             primos[ip++] = x;
             printf("%i:%i ", x, ip);
           }
       }
}   /**/


main(int argc, char **argv)
{
  int  np = 0, nps = 0, Lim = atoi(argv[1]);
  float   end_time, CPU_time;
  struct tms  buf;

     printf("\nLim: %i ---------------------------\n", Lim);
     mostra = FALSE;
     clock();
     np = calc_primos_div(Lim);   /**/
/*     nps = calc_primos_slow(Lim);  /**/
/*     calc_graf(Lim);   /**/
     end_time = clock();
     CPU_time = times(&buf);
     printf("\nTempo: %f seg   TempoCPU: %f seg   (CLOCKS_PER_SEC: %i)\n",
            end_time / CLOCKS_PER_SEC,
            CPU_time / CLOCKS_PER_SEC, CLOCKS_PER_SEC);
     printf("%i (%i) numeros primos calculados\n", np, nps);
     return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Além de só precisares de ver se os números são divisiveis por outros primos não precisas de avançar de 2 em 2. Todos os primos acima de 3 são formas de 6k+1 ou 6k-1.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora