Números primos até um limite dado.

[Inacabado]

Ola a todos estou de volta depois de uma longa ausência pois nao tenho pegado em C vai fazer uns meses valentes. Agora deu-me na mona e voltei a estudar/praticar um pouco.

Ora bem quis, por mim fazer um programa que procurasse primos ate um limite pedido. E o codigo que ate agora tenho e este:

 1 /*  */
  2 #include <stdio.h>
  3 
  4 int main(void)
  5 {
  6         int lim,i,j;
  7         lim=i=j=0; // inicializar as variaveis a zero para nao ficarem com "lixo"
  8         printf("Vamos encontrar numeros primos ate um limite dado.\n");
  9         printf("Insira um limite:\n");
 10         scanf("%d",&lim);
 11         printf("Numeros primos entre %d e %d:\n%d\n",0,lim,2);
 12         for(i=3;i<=lim;i+=2)//o dois e o unico primo par, por isso so percorre os numeros impares
 13         {
 14                 for(j=i-2;j>=3;j-=2)//se nao for primo sera divisivel por um dos impares ate 3 
 15                 {
 16                         if(i%j==0)
 17                                 break;
 18                         else    
 19                                 continue;
 20                         printf("%d\n",i);
 21                 }
 22         }
 23 return 0;
 24 }

Nao esta finalizado porque realmente encalhei ali no else. Ate uma determinada altura tinha a ideia limpa na minha cabeca de como fazer o programa. Mas de tanto pensar, encalhei mesmo naquela parte do código.

Eu sei que existem solucoes na internet mas queria seguir a minha linha de raciocínio e fazer a minha maneira.

Se me puderem dar uma ajuda, daquelas que me levem a desencalhar (uma indicação, um pequeno conselho), agradecia imenso. Mesmo assim ate voltar aqui vou continuar a insistir na solucao, pode ser que o resolva entretanto.

Abraco a todos e um cumprimento especial ao HappyHippo.

[Inacabado]

Ola a todos de novo, desencalhei! Eis o codigo como ficou:

  1 /* primeFind.c -- acha primos ate um limite pedido  */
  2 #include <stdio.h>
  3 
  4 int main(void)
  5 {
  6         int lim,i,j;
  7         lim=i=j=0; // inicializar as variaveis a zero para nao ficarem com "lixo"
  8         printf("Vamos encontrar numeros primos ate um limite dado.\n");
  9         printf("Insira um limite:\n");
 10         scanf("%d",&lim);
 11         printf("Numeros primos entre %d e %d:\n%d\n",0,lim,2);
 12         for(i=3;i<=lim;i+=2)//o dois e o unico primo par, por isso so percorre os numeros impares
 13         {
 14                 for(j=i-2;j>=3;j-=2)//se nao for primo sera divisivel por um dos impares ate 3 
 15                 {
 16                         if(i%j==0)
 17                                 break;
 18                         if(j==3) // se o valor de j chegar ate ao 3 significa que i e primo
 19                                 printf("%d\n",i);
 20                 }       
 21         }               
 22 return 0;
 23 }

 E tao bom chegarmos a solução pela nossa cabeça! E uma espécie de climax mental!!!  

Ao que parece o código corre que nem ginjas. Agora alguma sugestão, poderia estar melhor?

Estou contente, abraco a todos!

[Inacabado]

p.s. Vou ver se passo a participar mais no forum. Obrigado por existirem, este lugar e muito bom!

[HappyHippyHippo]

desculpa só ver o tópico agora. ainda bem que chegaste a uma solução, posso por em duvida a sua veracidade ?

a regra de um número ser primo é:
- O número é primo se e só se for divisível por 1 ou por ele próprio (claro que estamos a falar em |N).

mas essa regra tem uma segunda interpretação:
- O número é primo que não for possível criar uma factorização este em número primos.

dou-te uns exemplos de números que não são primos:
9 = 3x3
27 = 3x3x3
231 = 3x7x11

vamos agora validar o teu código:
- se nao for primo sera divisivel por um dos impares ate 3

se eu arranjar um número que a sua faactorização não tenha um número impar, então a suposição está incorrecta:
- 2x2x2 = 8

8 não é divisivel por um número impar, no entanto não é primo
conclusão : o código está errado.

----------

por outro lado, a regra que te apresentei deu origem aos metodos actuais de verificação de números primos:
- se o número a verificar for divisível por um número, então este faz parte da sua factorização, o que implica que basta verificar os números primos até ao número a verificar

melhoramento (programação dinâmica) : ir guardando os números primos obtidos e só verificar estes
 

[Warrior]

1 hour ago, HappyHippyHippo said:

se eu arranjar um número que a sua faactorização não tenha um número impar, então a suposição está incorrecta:
- 2x2x2 = 8

8 não é divisivel por um número impar, no entanto não é primo
conclusão : o código está errado.

Repara que ele colocou explícito o facto de, tirando o número 2, o número precisar de ser ímpar para poder ser primo.

1 hour ago, HappyHippyHippo said:

melhoramento (programação dinâmica) : ir guardando os números primos obtidos e só verificar estes

Isso seria uma melhoria, mas não é programação dinâmica.

 

Um aperfeiçoamento muito comum (e que faz MUITA diferença), é reparar que um número composto é necessariamente da forma a = b*c. Isso significa que, se o número for composto, então possui sempre um factor menor ou igual a sqrt(a), porque "b" e "c" não pode ser os dois, simultaneamente, maiores do que sqrt(a). Portanto não precisas de testar todos os números entre 3 e "i-2", podes só testar os números entre 3 e "<= sqrt(i)".

[HappyHippyHippo]

3 minutes ago, Warrior said:

Repara que ele colocou explícito o facto de, tirando o número 2, o número precisar de ser ímpar para poder ser primo.

pois ... mas a explicaçao é usada demonstrar um contra exemplo de como o código dele está incorrecto

a analisar o código de cabeça, parece-me que todos os números da gama 2^n são validados como primos simplesmente porque a sua factorização não envolve um único número impar.

3 minutes ago, Warrior said:

Isso seria uma melhoria, mas não é programação dinâmica.

hum ? desculpa mas é sim

source : https://en.wikipedia.org/wiki/Dynamic_programming

Quote

In computer science, mathematics, management science, economics and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions

- partir o problema em partes : calcular os primos até i-1

- guardar as soluções para obter o resultado final : usar os números primos até i-1 para saber se i é primo ou não.

no meu ponto de vista é tradução directa da definição

[Warrior]

Não quero poluir este tópico com conceitos de DP, principalmente quando o autor do tópico é um iniciante. Se quiseres desenvolver, tenho todo o gosto em mover a discussão para outro tópico.

A aplicação só seria directa caso se estivesse, actualmente, a calcular os primos até i-1 recursivamente. É complicado de explicar sem dar o código porque ninguém faria isto na prática, mas seria um caso em que para se saber se o número "i" é primo, verificamos se "i-2" é primo, e para verificar se "i-2" é primo verificamos se "i-4" é primo, recursivamente, dando uma complexidade exponencial. Se fosses passar dessa abordagem para o código actual, concordaria que estarias a usar DP. Não é esse o caso. No caso actual, os primos até i-1 nem sequer são calculados - só são algo que podemos usar para acelerar, tal como sugeriste.

[Inacabado]

10 horas atrás, HappyHippyHippo disse:

se eu arranjar um número que a sua faactorização não tenha um número impar, então a suposição está incorrecta:
- 2x2x2 = 8

8 não é divisivel por um número impar, no entanto não é primo
conclusão : o código está errado.
 

Mas o código nunca vai considerar nenhum numero par. Pois não existem pares primos, a excepcao do 2.

Como se pode ver vai de impar em impar (a existirem primos estão no grupo dos impares(salvo o numero 2)).

Portanto com todo o respeito fazer a afirmação de que o código está mal parece-me muito radical. Na pratica o código retorna todos os primos ate qualquer limite.

Se esse limite for o 8, retorna os primos "impares" ate 8. Múltiplos de 2 (todos os pares) estão fora da equação!

Muito obrigado e vou melhorar o código como o Warrior sugeriu. Muito obrigado aos dois!

Edited February 17, 2017 at 09:33 PM by Inacabado

[Inacabado]

9 horas atrás, Warrior disse:

Um aperfeiçoamento muito comum (e que faz MUITA diferença), é reparar que um número composto é necessariamente da forma a = b*c. Isso significa que, se o número for composto, então possui sempre um factor menor ou igual a sqrt(a), porque "b" e "c" não pode ser os dois, simultaneamente, maiores do que sqrt(a). Portanto não precisas de testar todos os números entre 3 e "i-2", podes só testar os números entre 3 e "<= sqrt(i)".

Essa observação e muito porreira! Neste caso teria de testar todos os impares ate a sqr(lim), ou mesmo todos os numeros. Considerando que fossem todos os numeros ate a sqr(lim), ja estaria a poupar trabalho ao processador. sinceramente vou aprofundar para perceber esse conceito de numeros compostos. Muito obrigado pelo excelente apontamento.

[Warrior]

Um número composto é simplesmente um número não-primo.

[Inacabado]

boas de novo. Agora estou mais a tentar blindar o programa de maneiras a que se o utilizador inserir um carácter nao-numérico, o programa continue a pedir um input, e so corre quando o caracter for numerico.

De certeza que tenho um erro de sintaxe, pois o programa esta a entrar em loop infinito.

Eis o codigo neste momento:

  1 /* primeFind.c -- acha primos ate um limite pedido  */
  2 #include <stdio.h>
  3 
  4 int main(void)
  5 {
  6         int lim,i,j;
  7         lim=i=j=0; // inicializar as variaveis a zero para nao ficarem com "lixo"
  8         printf("Vamos encontrar numeros primos ate um limite dado.\n");
  9         do
 10         {
 11                 printf("Insira um limite:\n");
 12                 scanf("%d",&lim);
 13         } while ((scanf("%d",&lim)) == 0 );
 14         printf("Numeros primos entre %d e %d:\n%d\n",0,lim,2);
 15         for(i=3;i<=lim;i+=2)//o dois e o unico primo par, por isso so percorre os numeros impares
 16         {
 17                 for(j=i-2;j>=3;j-=2)//se nao for primo sera divisivel por um dos impares ate 3 
 18                 {
 19                         if(i%j==0)
 20                                 break;
 21                         if(j==3) // se o valor de j chegar ate ao 3 significa que i e primo
 22                                 printf("%d\n",i);
 23                 }
 24         }
 25 return 0;
 26 }

Agradecia uma ajuda por favor.

Quanto a questão dos números compostos vou-me a ela logo que resolva este imbróglio.

Pelo que entendi um numero composto pode ser expresso na forma  n= m * m, em que pelo menos um dos factores e menor ou igual a sqr(n). Pois se ambos fossem maiores que a sqr(n) o numero seria maior que n.

exemplo: 16 = 4 * 4

Pela lei que o Warrior me deu eu só tenho que averiguar se sqr(m) tem factores primos alem de 1 e m -o que indicaria que nao era primo! - ou caso contrario seria primo.

Agora surge um problema, suponhamos o numero 30. vamos achar a sqr(30) e obtemos 5.48 arredondado a 2 c.d. Ora como e que eu vou fazer a verificacao em numeros reais como este? A trabalhar com inteiros a variável int vai arredondar a sqr(30) → 5 que e primo, mas 30 nao e primo! Quanto muito teria de arredondar para o inteiro mais próximo no sentido positivo →6 que nao e primo, o que condiz com 30. Acredito que tenho aqui umas voltinhas para dar, mas e sempre interessante...

Mas agora agora tenho este problema com o do while (). Muito obrigado pela paciência.

[HappyHippyHippo]

o que estou a ver no teu ciclo são dois scanfs seguidos, um dentro do corpo do do..while, e outro na verificação deste

um número composto não é n= m*m, mas sim n = m*k, o que estou a dizer é que os números usados para a composição não sáo necessariamente iguais

[Warrior]

Exactamente.

No caso do 30, tal como disseste, sqrt(30) ~= 5.48, o que significa que 30, se for um número composto (ou seja, se não for primo), possui um dos seus divisores <= 5. No caso de 30 até são todos, porque 30 = 2x3x5, de modo que ao testares 30 % 2 == 0 podes logo parar.

[Inacabado]

3 horas atrás, Warrior disse:

Exactamente.

No caso do 30, tal como disseste, sqrt(30) ~= 5.48, o que significa que 30, se for um número composto (ou seja, se não for primo), possui um dos seus divisores <= 5. No caso de 30 até são todos, porque 30 = 2x3x5, de modo que ao testares 30 % 2 == 0 podes logo parar.

Percebi perfeitamente. acho que tenho que aprender a ler/escutar porque já tinhas frisado precisamente isso quando disseste la atrás:

Em 17/02/2017 às 12:01, Warrior disse:

 Portanto não precisas de testar todos os números entre 3 e "i-2", podes só testar os números entre 3 e "<= sqrt(i)".

E estava tao concentrado na parte dos números compostos que descuidei a ultima parte do teu comentário.

Ou seja para melhorar o codigo o segundo ciclo for seria "grosso modo" algo do genero:

 for(j=sqrt(i);j>=3;j-=2)

Certo?

Edited February 19, 2017 at 05:36 PM by Inacabado

[Inacabado]

3 horas atrás, HappyHippyHippo disse:

o que estou a ver no teu ciclo são dois scanfs seguidos, um dentro do corpo do do..while, e outro na verificação deste

Neste momento tenho o codigo assim:

  9         while ((scanf("%d",&lim))==0)
 10         {
 11                 printf("Insira um limite:\n");
 12                 scanf("%d",&lim);
 13         }

E o codigo continua em loop infinito.

Ou seja continuo com dois scanfs, mas julgo serem necessarios, ou nao?

O primeiro testa se o scanf recebeu um inteiro, o segundo serve para eventual saida do while e seguimento do código!

Onde e que esta o meu erro? Ajude-me por favor. Obrigado.

[Inacabado]

Agora agora alterei aquela parte do codigo para

 status=scanf("%d",&lim);
 10         while (status==0)
 11         {
 12                 printf("Insira um limite:\n");
 13                 status=scanf("%d",&lim);
 14         }

 

Mas continua a nao dar. No problem, eu nao desisto... hehe...

Nao tem nada a ver com o buffer do teclado? lembro-me de o HHH ter falado nisso algures... sera isso?

Resolvi com o getchar(). Fiz uma pesquisa e outro forum deu a opcao do getchar().

ficou assim o codigo:

  9         status=scanf("%d",&lim);
 10         getchar();
 11         while (status==0)
 12         {
 13                 printf("Insira um limite:\n");
 14                 status=scanf("%d",&lim);
 15                 getchar();
 16         }

Agora nem sei porque e que funciona e o que falhava antes. Vou fazer uma pesquisa.

Por outro lado ouvi dizer que a funcao getchar () nao e segura...

Ate breve, abracos e obrigado

Edited February 19, 2017 at 06:19 PM by Inacabado
update,

[HappyHippyHippo]

tira o getchar e metenum espaço antes do %d.

sum e do buffer de leitura

[Inacabado]

Depois de mais um dia de trabalho braçal aqui o empregado de armazém, voltou ao mundo do refinamento intelectual (nem que seja para mostrar a ele próprio de que e mais qualquer coisa...), para aprimorar o seu programa de achar primos ate um dado limite.

Código final para este pequeno desafio de iniciante, e oferta de mim para quem queira (desde que estude o codigo e compreenda!):

 1 /* primeFind.c -- acha primos ate um limite pedido  */
  2 #include <stdio.h>
  3 #include <math.h>
  4 
  5 int main(void)
  6 {
  7         int lim,i,j;
  8         lim=i=j=0; // inicializar as variaveis a zero para nao ficarem com "lixo"
  9         printf("Vamos encontrar numeros primos ate um limite dado.\n");
 10         printf("Insira um limite:\n");
 11         while ((scanf("%d",&lim))==0)
 12         {
 13                 printf("Insira um limite numerico!\n");
 14                 scanf("%d",&lim);
 15                 getchar();
 16         }
 17         printf("Numeros primos entre %d e %d:\n%d\n",0,lim,2);
 18         for(i=3;i<=lim;i+=2)//o dois e o unico primo par, por isso so percorre os numeros impares
 19         {
 20                 for(j=sqrt(i);j>=2;j--)//se i nao for primo a sqr de i sera divisivel por um dos digitos ate 2 
 21                 {
 22                         if(i%j==0)
 23                                 break;
 24                         if(j==2) // se o valor de j chegar ate ao 2 significa que i e primo
 25                                 printf("%d\n",i);
 26                 }
 27         }
 28 return 0;
 29 }

Ja com a sqrt(i), essa preciosa dica do nosso amigo warrior - o codigo fica mesmo muito mais eficiente!

Abracos e beijinhos a todos, estou feliz!

Edited February 20, 2017 at 09:32 PM by Inacabado
correção

[HappyHippyHippo]

agora imagina se fizestes a optimização que te disse ...

[Warrior]

Acabaste por não resolver o problema da leitura. Repara que o código obrigatoriamente passa por um número ímpar de scanfs, o que não devia ser necessário. A estrutura correcta é usar um do { } while(scanf()), possivelmente com um fflush() dentro do ciclo, dependendo do que quiseres fazer.

Já agora, alguém consegue:

1. Analizar a complexidade temporal da ideia inicial do "Inacabado"?
2. Analizar a complexidade temporal com a melhoria do sqrt()?
3. Analizar a complexidade temporal com a sugestão do HHH (i.e., iterar só sobre os primos, possivelmente até sqrt())?

Edited February 21, 2017 at 10:03 AM by Warrior