Exercicios Programação

Qual é a dúvida nesse exercício? Como descobrir se um número é primo? Como implementá-lo?

Utiliza-se o operador % ( pelo menos em C e derivados ) para saber o resto de uma divisão. Se o resto da divisão de um número for 0 apenas para a divisão por 1 e ele próprio então é primo.

9 % 2 != 0
9 % 3 == 0

9 não é primo, 9 / 3 = 3.

5 % 2 != 0
5 % 3 != 0
5 % 4 != 0

5 é primo.

Agora é só aplicar um ciclo com este raciocínio, depois entram então as optimizações, mas isso também é só matemática.

EDIT:
Se ainda não sabes o que é a raiz quadrada se calhar é melhor não ires por aí mas se tiveres interesse:
É a operação inversa da potência.

3^2 = 9 ( 3 * 3 )

raíz quadrada de 9 = 3 ( 3^2 = 9 );

Em vez de dividires o número pelos números até n, podes apenas dividir até à raiz quadrada de n. Para não ter que utilizar a função da raiz quadrada também dá dividindo enquanto n * n < número a testar.

Mas outra optimização muito eficaz:
Utilizar apenas números ímpares tanto no número a testar como nos divisores ( excepto o 2 ).
 
Última edição:
Qual é a dúvida nesse exercício? Como descobrir se um número é primo? Como implementá-lo?

Utiliza-se o operador % ( pelo menos em C e derivados ) para saber o resto de uma divisão. Se o resto da divisão de um número for 0 apenas para a divisão por 1 e ele próprio então é primo.

9 % 2 != 0
9 % 3 == 0

9 não é primo, 9 / 3 = 3.

5 % 2 != 0
5 % 3 != 0
5 % 4 != 0

5 é primo.

Agora é só aplicar um ciclo com este raciocínio, depois entram então as optimizações, mas isso também é só matemática.

EDIT:
Se ainda não sabes o que é a raiz quadrada se calhar é melhor não ires por aí mas se tiveres interesse:
É a operação inversa da potência.

3^2 = 9 ( 3 * 3 )

raíz quadrada de 9 = 3 ( 3^2 = 9 );

Em vez de dividires o número pelos números até n, podes apenas dividir até à raiz quadrada de n. Para não ter que utilizar a função da raiz quadrada também dá dividindo enquanto num * num < n ( num = número a testar ).

Mas outra optimização muito eficaz:
Utilizar apenas números ímpares tanto no número a testar como nos divisores.

Podes estar descansado que sei perfeitamente verificar se um número é primo ou não.:D A teoria não é problema. Também estou completamente à vontade com raizes quadradas. (Terminei o 12º.)
O problema é traduzir isso para python e para um ciclo. (Isto porque ainda estou no principio e não tenho tanta prática como isso. (Quase nenhuma, aliás)).
Podes dar um empurrão na parte do código?
 
Podias ter dito, como nem tens a idade no perfil não adivinho o que já sabes. :p

Muito rápido e básico é isto em C, não sei se é parecido com python.

Código:
for( n = 3; n < limite; n += 2 )
   {
   for( d = 2; d * d < n; d++ )
      {
      if( n % d == 0 ) printf(" Não é primo! ");
      }
   }

É mesmo só o básico, nem diz se é primo, apenas diz se não é primo e continua na mesma.
 
Podias ter dito, como nem tens a idade no perfil não adivinho o que já sabes. :p

Muito rápido e básico é isto em C, não sei se é parecido com python.

Código:
for( n = 3; n < limite; n += 2 )
   {
   for( d = 2; d * d < n; d++ )
      {
      if( n % d == 0 ) printf(" Não é primo! ");
      }
   }
É mesmo só o básico, nem diz se é primo, apenas diz se não é primo e continua na mesma.

Tenho idade sim. 17 :D
E esse ciclo determina os n primeiros números primos?
 
Tenho idade sim. 17 :D
E esse ciclo determina os n primeiros números primos?
Este novo layout do perfil enganou-me... :X

Aquele exemplo era mais só para mostrar a lógica de achar se é primo, para funcionar como o pretendido é mais assim:

Código:
for( n = 3; n < limite; n += 2 )
   {
   int z = 0
   for( d = 2; d * d < n; d++ )
      {
      if( n % d == 0 )
         {
         z++;
         break;
         }
      }
   if( z == 0 ) printf( "%d\n", n );
   }
 
Again, se não sabias fazer um ciclo for, aconselho-te vivamente a aprofundar mais um bocadinho a linguagem antes de partires para isto ;)

Pelo menos aprende a usar bem o for, while, if e switch :P
 
Não sabia :)

Mas uma alternativa ao switch é o if...else if (else if, elseif, elsif, whatever :P).
Código:
switch(var) {
 case a: expr1; break;
 case b: expr2; break;
 default: expr3; break;
}
ou
Código:
if(var == a)
 expr1;
else if(var == b)
 expr2;
else
 expr3;
 
Exacto. Em Python não há switch. Tem que ser criado manualmente. No exame de uma cadeira em que a linguagem era Python, tinha uma questão em que se pretendia exactamente isso ;)

Quanto ao problema em questão:

Código:
from math import sqrt
def primo(num):
    if num<4:
        return 1
    elif num%2==0:
        return 0
    else:
        for i in range(2,int(sqrt(num))+1):
            if num%i==0:
                return 0
    return 1
                
def main():
    i=0
    z=1
    n=input("Insira n\n")
    while i<n:
        z+=1
        if primo(z):
            i+=1
            print "Primo -> ",z

if __name__=="__main__":
    main()
 
Última edição:
Optimização:
Para qualquer n, não é possível dividí-lo por qualquer número entre raíz quadrada de n e n.

Asneirada.

-> sqrt (36) = 6
-> 12 > 6, 18 > 6, 36 > 6
-> 36%12 = 0, 36%18 = 0, 36%36 = 0

O teorema dos divisores de um número é: Para qualquer número natural n, o único divisor de n maior do que n/2 é o próprio n.

Agora aquilo que tu querias dizer, e que disseste +/- na 2ª frase do spoiler, é que não valia a pena testar os números no intervalo [sqrt(n),n], para determinar se n é primo!. Se no intervalo [2,sqrt(n)] existir algum número que seja divisor de n, então n não é primo!. Isto porque, se n não é primo, então pode ser determinado por: n = a*b, com a<=b (ou vice-versa), sendo a (ou b, caso b<=a) sempre menor do que sqrt(n). Ler.
 
Última edição:
Tens razão.
É óbvio que entre n/2 e n não era mesmo possível dividir por qualquer número. Entretanto, disseram-me que não valia a pena dividir por qualquer número superior à raíz quadrada de n. Devo ter assumido incorrectamente o resto :x

(5 minutos depois) Sim, foi isso mesmo:
angelofwisdom, afinal pode-se mesmo só verificar se um número é primo dividindo até à raiz quadrada do número em vez de dividir até metade do número.

http://www.upgaming-hq.com/cd_ioi_05/manual/math.html
http://www.educ.fc.ul.pt/icm/icm98/icm12/Algoritmos.htm

Deduzo que seja por um número que tenha um divisor maior que a raiz quadrada ter de ter obrigatoriamente um divisor menor que a raiz, portanto basta verificar com divisores até à raiz.

Foi má interpretação da minha parte. Peço desculpa por isso :x
 
Asneirada.

-> sqrt (36) = 6
-> 12 > 6, 18 > 6, 36 > 6
-> 36%12 = 0, 36%18 = 0, 36%36 = 0

O teorema dos divisores de um número é: Para qualquer número natural n, o único divisor de n maior do que n/2 é o próprio n.

Agora aquilo que tu querias dizer, e que disseste +/- na 2ª frase do spoiler, é que não valia a pena testar os números no intervalo [sqrt(n),n], para determinar se n é primo!. Se no intervalo [2,sqrt(n)] existir algum número que seja divisor de n, então n não é primo!. Isto porque, se n não é primo, então pode ser determinado por: n = a*b, com a<=b (ou vice-versa), sendo a (ou b, caso b<=a) sempre menor do que sqrt(n). Ler.

Exacto. Por acaso limitei-me a ler a parte dos switch e a colocar a resolução sem ter lido os posts anteriores.

Acrescento mais...

Se quiseres factorizar um número em 2 primos (número que não pode ser primo), sabes que um dos factores irá ser menor que sqrt(num) e outro maior que essa raiz.
 
Última edição pelo moderador:
Boas,
Tive a ver o tópico e estava a tentar fazer o exercício 6 (em c++) que é o seguinte:

6 - um programa que determina os primeiros n números primos, sendo n um número definido pelo utilizador.
Como número primo entenda-se "número inteiro que apenas é divisível por ele mesmo e por 1".


Depois de ter lido isto fiquei com a ideia que o programa devia ser o seguinte:
pedir um valor (por exemplo 5) e depois devolver os 5 primeiros numeros primos (2,3,5,7,11), mas depois li isto:

Definição de número primo: "número inteiro apenas divisível por ele mesmo e por 1".
Como determiná-lo? Tentativa e erro - dividir por cada um dos números inteiros entre 2 (porque por 1 são todos divisíveis) e ele mesmo - 1 (porque por ele mesmo é sempre 1). Ou seja, para qualquer n, dividir por todos os números inteiros do intervalo ]1, n[

E fiquei sem perceber o quê que se tem de fazer afinal no exercício...será que alguém me pode explicar o quê que se pretende afinal???

E já agora dar uma ajuda, porque não estou muito bem a ver como é que o exercício se faz.


Cumps
 
O primeiro quote diz o exercício - "quais são os primeiros n números primos?" (para n=5, resposta = {2,3,5,7,11})
O segundo quote diz como determinar que um determinado número é primo (para qualquer número, a resposta é True ou False - primo ou não primo)

Fazes o que o segundo quote diz tantas vezes quantas necessárias até "preencheres" o primeiro quote.

Ou seja,
O segundo quote "define" uma função simples (há que realçar que a função é bastante simples - tentativa e erro) que determina a primalidade de um número. Colocando isso dentro de um ciclo while (em princípio), essa função é executada várias vezes - tantas quantas necessárias até que sejam descobertos n números primos.
Por exemplo, para n=5, são testados os números 2,3,4,5,6,7,8,9,10 e 11, e a função retorna True em 2,3,5,7 e 11, sendo que quando o ciclo chega ao 11, o while termina porque já foram descobertos 5 números (#{2,3,5,7,11} = 5)

Só uma pergunta cujas opiniões, pelos vistos, variam: 1 é primo? Há alguma convenção que defina isso de uma vez por todas?
 
O primeiro quote diz o exercício - "quais são os primeiros n números primos?" (para n=5, resposta = {2,3,5,7,11})
O segundo quote diz como determinar que um determinado número é primo (para qualquer número, a resposta é True ou False - primo ou não primo)

Fazes o que o segundo quote diz tantas vezes quantas necessárias até "preencheres" o primeiro quote.

Ou seja,
O segundo quote "define" uma função simples (há que realçar que a função é bastante simples - tentativa e erro) que determina a primalidade de um número. Colocando isso dentro de um ciclo while (em princípio), essa função é executada várias vezes - tantas quantas necessárias até que sejam descobertos n números primos.
Por exemplo, para n=5, são testados os números 2,3,4,5,6,7,8,9,10 e 11, e a função retorna True em 2,3,5,7 e 11, sendo que quando o ciclo chega ao 11, o while termina porque já foram descobertos 5 números (#{2,3,5,7,11} = 5)

Só uma pergunta cujas opiniões, pelos vistos, variam: 1 é primo? Há alguma convenção que defina isso de uma vez por todas?

O 1 não é primo, porque só possui um divisor (ele proprio) e um numero primo é um numero que é divisível por 2 e só 2 numeros (o 1 e ele próprio).

Não sei se esta pergunta é muito estúpida, mas o que é que é o spoiler??
 
O primeiro quote diz o exercício - "quais são os primeiros n números primos?" (para n=5, resposta = {2,3,5,7,11})
O segundo quote diz como determinar que um determinado número é primo (para qualquer número, a resposta é True ou False - primo ou não primo)

Fazes o que o segundo quote diz tantas vezes quantas necessárias até "preencheres" o primeiro quote.

Ou seja,
O segundo quote "define" uma função simples (há que realçar que a função é bastante simples - tentativa e erro) que determina a primalidade de um número. Colocando isso dentro de um ciclo while (em princípio), essa função é executada várias vezes - tantas quantas necessárias até que sejam descobertos n números primos.
Por exemplo, para n=5, são testados os números 2,3,4,5,6,7,8,9,10 e 11, e a função retorna True em 2,3,5,7 e 11, sendo que quando o ciclo chega ao 11, o while termina porque já foram descobertos 5 números (#{2,3,5,7,11} = 5)

Só uma pergunta cujas opiniões, pelos vistos, variam: 1 é primo? Há alguma convenção que defina isso de uma vez por todas?

Pelo que eu li, o 1 não é primo. Tinha-me escapado isso no meu código acima, mas já corrigi ;)
 
A definição que me deram de número primo é que é "um número que apenas é divisível por ele mesmo e por 1", pelo que ele mesmo ser 1 seria irrelevante para o assunto. 1 é divisível por ele mesmo e por 1, ainda que sejam o mesmo, e não é divisível por mais nada, logo, seria primo.
Se a definição "oficial" disser que é um número apenas divisível por 2 números, então finalmente acredito que 1 não seja primo.

O spoiler é uma tag que esconde o texto, uma vez que a sua leitura pode "estragar uma surpresa". Imagina que alguém conta o final de um filme num tópico e tu ainda não viste o filme - o spoiler serve para não leres nada que to estrague ;)
Neste caso específico, eu pus aquilo assim porque está a servir de resposta ao exercício, e assim perde a piada :P para o leres, só tens de marcar o texto (como se o fosses copiar).
 
Back
Topo