Ir ao conteúdo
  • Comunicados

    • Gabriel Torres

      Seja um moderador do Clube do Hardware!   12-02-2016

      Prezados membros do Clube do Hardware, Está aberto o processo de seleção de novos moderadores para diversos setores ou áreas do Clube do Hardware. Os requisitos são:   Pelo menos 500 posts e um ano de cadastro; Boa frequência de participação; Ser respeitoso, cordial e educado com os demais membros; Ter bom nível de português; Ter razoável conhecimento da área em que pretende atuar; Saber trabalhar em equipe (com os moderadores, coordenadores e administradores).   Os interessados deverão enviar uma mensagem privada para o usuário @Equipe Clube do Hardware com o título "Candidato a moderador". A mensagem deverá conter respostas às perguntas abaixo:   Qual o seu nome completo? Qual sua data de nascimento? Qual sua formação/profissão? Já atuou como moderador em algo outro fórum, se sim, qual? De forma sucinta, explique o porquê de querer ser moderador do fórum e conte-nos um pouco sobre você.   OBS: Não se trata de função remunerada. Todos que fazem parte do staff são voluntários.
    • DiF

      Poste seus códigos corretamente!   21-05-2016

      Prezados membros do Fórum do Clube do Hardware, O Fórum oferece um recurso chamado CODE, onde o ícone no painel do editor é  <>     O uso deste recurso é  imprescindível para uma melhor leitura, manter a organização, diferenciar de texto comum e principalmente evitar que os compiladores e IDEs acusem erro ao colar um código copiado daqui. Portanto convido-lhes para ler as instruções de como usar este recurso CODE neste tópico:  
Henrique Vieira Prata

C Números primos positivos em C

Recommended Posts

Alguém pode me dizer porque esse código não serve pra identificar os números primos positivos?

Só pode usar a biblioteca stdio.h e math.h. Alem disso só pode usar até estruturas de repetição(while).

#include<stdio.h>

int main ()
{
    int a;
    
    scanf("%d",&a);
    
    if((a!=2 && a!=3 && a!=5 && a!=7)&& ((a%2)==0 || (a%3)==0 || (a%5)==0 || (a%7)==0) || a==1 || a==0)
    
    printf("NAO PRIMO\n");
    
    else
    
    printf("PRIMO\n");

    return 0;
}

 

Editado por DiF
Inserir os códigos com o botão CODE <>

Compartilhar este post


Link para o post
Compartilhar em outros sites
  • Autor do tópico
  • 29 minutos atrás, Xaws disse:

    @Henrique Vieira Prata  O que ta dando ai? Testei aqui e funcionou normal

    Eu upo o codigo pro site que testa (sharif) ele fala ue ta errado. 175 de 200 pontos. Mas o site maldito não fala o qie ta errado!

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Lol, eu lembro de ter cometido esse mesmo erro em 2009 em uma competição (ou foi na OBI?) quando eu tava começando a programar em C :P.

     

    Se um número não é divisível por 2, 3, 5 ou 7 não significa que seja primo. Por exemplo, 121 = 11*11 e portanto não é primo, mas seu código dirá que é porque não é divisível por nenhum primo de 2 a 7.

     

    Não tem como você colocar todos os primos na mão aí... vai ter que usar um laço de repetição.

    adicionado 2 minutos depois

    Ah, mais uma dica pra acelerar o código. Mas só leia este comentário depois de conseguir fazer funcionar do jeito mais simples possível.

     

    Você não precisa checar se o número N é divisível por algum número entre 2 e N-1. Pode verificar apenas se é divisível por algum número entre 2 e raiz(N).

    Editado por RafaelCLP

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
  • Autor do tópico
  • 1 hora atrás, RafaelCLP disse:

    Lol, eu lembro de ter cometido esse mesmo erro em 2009 em uma competição (ou foi na OBI?) quando eu tava começando a programar em C :P.

     

    Se um número não é divisível por 2, 3, 5 ou 7 não significa que seja primo. Por exemplo, 121 = 11*11 e portanto não é primo, mas seu código dirá que é porque não é divisível por nenhum primo de 2 a 7.

     

    Não tem como você colocar todos os primos na mão aí... vai ter que usar um laço de repetição.

    adicionado 2 minutos depois

    Ah, mais uma dica pra acelerar o código. Mas só leia este comentário depois de conseguir fazer funcionar do jeito mais simples possível.

     

    Você não precisa checar se o número N é divisível por algum número entre 2 e N-1. Pode verificar apenas se é divisível por algum número entre 2 e raiz(N).

    Eu sabia que estava errado desde o começo mas não sabia porque. Eu tentei fazer o Crivo de Eratóstenes mas eu também não entendi direito o crivo. E sei que o crivo só funciona até um certo número. E também não entendi porque acertei 175 de 200.

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    @Henrique Vieira Prata  Ah nesse caso ai eu não sei cara, nem sei o que é esse sharif kkk, já testou pra ver se não são as chaves que você deixou sem? 

     

    #include<stdio.h>
    
    int main ()
    {
        int a;
        
        scanf("%d",&a);
        
        if((a!=2 && a!=3 && a!=5 && a!=7)&& ((a%2)==0 || (a%3)==0 || (a%5)==0 || (a%7)==0) || a==1 || a==0)
        { //aqui
        printf("NAO PRIMO\n");
        }// aqui
        else
        { //aqui
        printf("PRIMO\n");
    
        return 0;
    } //e +1 aqui
      }

     Não sei se tem algo haver mais tenta ai, foi mal não poder ajudar

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
    1 hora atrás, Henrique Vieira Prata disse:

    Eu sabia que estava errado desde o começo mas não sabia porque. Eu tentei fazer o Crivo de Eratóstenes mas eu também não entendi direito o crivo. E sei que o crivo só funciona até um certo número. E também não entendi porque acertei 175 de 200.

    O crivo funciona até qualquer número na verdade, só que é limitado pela quantidade de memória (se quiser saber se um número N é primo, precisa de raiz(N) de memória). Mas pra essa questão você não precisa dele, pode ir com a solução simples mesmo. Se quiser entender o crivo, posso te explicar.

    • Curtir 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
  • Autor do tópico
  • 4 horas atrás, RafaelCLP disse:

    O crivo funciona até qualquer número na verdade, só que é limitado pela quantidade de memória (se quiser saber se um número N é primo, precisa de raiz(N) de memória). Mas pra essa questão você não precisa dele, pode ir com a solução simples mesmo. Se quiser entender o crivo, posso te explicar.

    Explica pra mim pf.

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Números primos e compostos

    Número primo: um inteiro maior do que 1 é dito primo se possui exatamente dois divisores inteiros positivos: 1 e x.

    Número composto: todo inteiro maior do que 1 que não é primo é dito composto.

     

    Por exemplo:

    - 7 é primo porque os únicos inteiros positivos que dividem 7 são 1 e 7.

    - 21 não é primo porque é divisível por 1, 3, 7 e 21, possuindo quatro divisores. Logo, é composto.

     

    Todo número composto pode ser fatorado em um produto de números primos. Por exemplo, 42 = 2 * 3 * 7.

     

    Isso significa que pra gerar um número composto basta pegar 2 ou mais números primos (não necessariamente distintos) e multiplicá-los. Exemplos:

    - 2 * 2 = 4

    - 3 * 5 = 15

    - 3 * 5 * 7 = 105

    Não preciso nem falar que se multiplicarmos qualquer número composto por qualquer outro inteiro positivo teremos um número composto. Se isso não está óbvio pra você, releia até ficar.

     

    Crivo

    Vamos encontrar todos os primos até n. A ideia do Crivo é bem simples. Vamos nos basear no fato de que se um número x é primo, então 2x, 3x, 4x, ..., ⌊n/x⌋x não são primos. Isso é óbvio, porque se multiplicamos um primo por qualquer outro número inteiro maior que 1 ele vira composto. Ou seja, todo múltiplo de um primo é composto...

     

    O primeiro passo do crivo consiste em:

    1. Criar um array ehPrimo de tamanho n+1 e marcar ehPrimo[x] para x > 1 com o valor 1. Aqui, 1 indica que é primo, 0 indica que não é. Até que provemos que um número é composto, vamos assumir que ele é primo.

    int ehPrimo[n+1] = {0, 0};
    int i;
    for (i = 2; i <= n; i++) ehPrimo[i] = 1;

     

    Agora, vamos criar um x = 2 e repetir os passos a seguir até chegarmos em x = n.

    1. Se x é primo, percorra todos os múltiplos de x (2x, 3x, 4x, ...) e marque-os como não primos, ou seja, ehPrimo[2x] = 0, ehPrimo[3x] = 0, ...

    2. Incremente x e volte para o passo 3.

    int x;
    for (x = 2; x <= n; x++) {
    	if (ehPrimo[x]) {
    		for (i = 2; i*x <= n; i++) ehPrimo[i*x] = 0;
    	}
    }

    Repare que ao fim do algoritmo, vamos ter marcado TODO múltiplo de um primo com 0. Já os números primos não são marcados, porque nós só marcamos números que podem ser obtidos pelo produto de outros dois números (maiores que 1): i*x. Se eu pudesse obter um número y pelo produto de i*x, esse y não seria primo, seria composto.

     

    Pronto, agora temos um array ehPrimo que nos diz se um certo número entre 0 e n é primo.

     

    Na Wikipedia tem um GIF bem interessante que mostra o funcionamento do algoritmo para n=120:

    https://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes#Visualiza.C3.A7.C3.A3o_do_Crivo

     

    Otimizações

    1. Em vez de começar a partir de i = 2, podemos começar a partir de i = x no segundo for. Podemos fazer isso porque ao chegar, por exemplo, no primo x = 7, já marcamos 2*7, 2*(2*7), 2*(3*7), ..., como não primo quando tínhamos x = 2; marcamos 3*7, 3*(2*7), ..., quando estavamos no x = 3; e marcamos 5*7, ..., no x = 5. Ou seja, todo i*7 com i < 7 já foi marcado em algum dos x anteriores, e podemos portanto começar do i = x.

     

    2. Podemos ir de x = 2 até raiz(n) em vez de ir até n. Se você entendeu a otimização 1, deve entender também porque isto funciona. O motivo é o mesmo.

     

    Editado por RafaelCLP
    • Curtir 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Crie uma conta ou entre para comentar

    Você precisar ser um membro para fazer um comentário






    Sobre o Clube do Hardware

    No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

    Direitos autorais

    Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

    ×