C Números primos positivos em C

Henrique Vieira Prata · 21 de setembro de 2017

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;
}

Xaws · 21 de setembro de 2017

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

Henrique Vieira Prata · 21 de setembro de 2017

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!

RafaelCLP · 21 de setembro de 2017

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 .

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).

Henrique Vieira Prata · 21 de setembro de 2017

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 .

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.

Xaws · 21 de setembro de 2017

@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

RafaelCLP · 21 de setembro de 2017

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.

Henrique Vieira Prata · 21 de setembro de 2017

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.

RafaelCLP · 22 de setembro de 2017

Números primos e compostos

Número primo: um inteiro x 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.