Programa em C++ para encontrar números primos

cesar15
(usa Ubuntu)

Enviado em 10/11/2015 - 10:31h

Tenho que criar um programa que o usuário digite um valor limite, e o programa vai listar todos os números primos dentro desse limite.

Por exemplo:

O usuário digita 5, e o programa lista todos os primos entre 1 e 5.

Como eu faço o código para verificar se um valor inteiro é primo ou não?

andr3ribeiro
(usa Arch Linux)

Enviado em 10/11/2015 - 10:38h

Dei uma pesquisada nesse site:
http://lmgtfy.com/?q=numeros+primos+em+C

e encontrei um link que fala isso:


-----------------------------------------------------------------------
MAC-110 - Numero Primo -- Três solucoes para o mesmo problema
=======================================================================

/* 

 * arquivo: primo1.c

 * --------------------

 * Este programa verifica se um dado numero inteiro positivo  n 

 * é primo 

 */





#include <stdio.h>



int main()

{

    int n,			/* numero a ser lido e testado */

     d,				/* candidato a divisor */

     EhPrimo;			/* para indicar se o numero dado n 'e primo ou nao     */

	/* Convencao: EhPrimo = 1 se o numero dado 'e primo */

	/*  EhPrimo = 0 se o numero dado nao 'e primo       */

   



    d = 2;

    EhPrimo = 1;		/* Ate' prova em contrario, supomos que n seja  primo */



    printf("Forneca um numero inteiro positivo ===> ");

    scanf("%d", &n);

    printf("Inteiro dado = %d \n", n);



    if (n <= 1)

	EhPrimo = 0;



    while (EhPrimo == 1 && d <= n / 2) {

	if (n % d  == 0)

	    EhPrimo = 0;

	d = d + 1;

    }



    if (EhPrimo == 1)

	printf("%d e' primo \n", n);

    else

	printf(" %d nao e' primo \n", n);



    return 0;

}

 

-------------------------------------------------------------------------


/*
* arquivo: primo2.c
* --------------------
* Este programa verifica se um dado numero inteiro positivo n
* é primo
*/

#include <stdio.h>

#define TRUE  1                   /* NOVIDADE!!! */

#define FALSE 0                   /* NOVIDADE!!! */



int main()

{

    int n,			/* numero a ser lido e testado */

     d,				/* candidato a divisor */

     EhPrimo,			/* para indicar se o numero dado n 'e primo ou nao     */

	/* Convencao: EhPrimo = 1 se o numero dado 'e primo */

	/*  EhPrimo = 0 se o numero dado nao 'e primo        */

     resto;

    d = 2;

    EhPrimo = TRUE;		/* Ate' prova em contrario, supomos que n seja  primo */



    printf("Forneca um numero inteiro positivo ===> ");

    scanf("%d", &n);

    printf("Inteiro dado = %d \n", n);



    if (n <= 1)

	EhPrimo = FALSE;



    while (EhPrimo == TRUE && d <= n / 2) {

	resto = n % d;

	if (resto == 0)

	    EhPrimo = 0;

	d = d + 1;

    }



    if (EhPrimo == TRUE)

	printf("%d e' primo \n", n);

    else

	printf(" %d nao e' primo \n", n);



    return 0;

}

 

----------------------------------------------------------------

Veja abaixo: comparacao com TRUE foi simplificada: fica subentendida!
Apenas os ímpares sao testados: 1, 3, 5...como possiveis
candidatos a divisor

/* 

 * arquivo: primo3.c

 * --------------------

 * Este programa verifica se um dado numero inteiro positivo  n 

 * é primo 

 */



#include <stdio.h>



#define TRUE 1

#define FALSE 0



int main()

{

    int n,			/* numero a ser lido e testado */

     d,				/* candidato a divisor */

     EhPrimo;			/* para indicar se o numero dado n 'e primo ou nao     */

	/* Convencao: EhPrimo = TRUE se o numero dado 'e primo */

	/*  EhPrimo = FALSE se o numero dado nao 'e primo        */

   



    printf("Forneca um numero inteiro positivo ===> ");

    scanf("%d", &n);

    printf("Inteiro dado = %d \n", n);





    if (n <= 1 || (n != 2 && n % 2 == 0))

	EhPrimo = FALSE;	/* nenhum numero inteiro <= 1 ou par > 2 e' primo */

    else

	EhPrimo = TRUE;		/* o numero e' primo ate que se prove o contrario */





    d = 3;

    while (EhPrimo  && d <= n / 2) {

	if (n % d == 0)

	    EhPrimo = 0;

	d = d + 2;		/* testamos so' os  impares: 3, 5, 7... */

    }



    if (EhPrimo)

	printf("%d e' primo \n", n);

    else

	printf(" %d nao e' primo \n", n);



    return 0;

}

 

uilianries
(usa Linux Mint)

Enviado em 10/11/2015 - 12:38h

Essa é uma forma não otimizada de validar um número primo, mas funciona:

static int eh_primo (int x) {    

    for (int i=2; i<x; ++i) {

        if (x%i == 0) {

            return 0;

        }

    }

    return 1;

}

 

paulo1205
(usa Ubuntu)

Enviado em 10/11/2015 - 13:09h

O algoritmo para obter todos os primos no intervalo [0; N] (ou [1; N], ou ainda [2; N], dado que 0 e 1 não são primos) se chama Crivo de Eratóstenes. Procure ler sobre ele, pois esse é *O* algortimo que você quer (desde que N não seja absurdamente grande). Qualquer outra resposta será pior, ainda que apresente uma saída correta.

Para testar se um número n em particular é primo, você só precisa testar a divisibilidade até a raiz quadrada de n. Algo como abaixo.

bool is_prime(unsigned n){

  // 2 é primo

  if(n==2)

    return true;



  // 0, 1 e todos os pares diferentes de 2 não são primos.

  if(n<2 || !(n&1))

    return false;



  unsigned i=3;

  while(i*i<=n){

    // (n%i)==0 implica n divisível por i, logo não é primo.

    if(!(n%i))

      return false;

    i+=2;

  }



  // Se chegou até aqui, não encontrou divisor para n.

  return true;

}