• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Guest tsenart

[Resolvido] Programa que apresenta os números primos de um intervalo.

12 mensagens neste tópico

Fiz este programa que apresenta os números primos de um intervalo dado pelo utilizador.

/* Program that finds prime numbers between a range.
* Copyright (C) 20/04/2007  Tomás Senart

* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.

* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*/

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    unsigned int num1 = 0, num2 = 0;
    int i, j, isprime = 0, count = 0, test = 0;

    printf("\nEnter a range of numbers(e.g. '100 200')(MAX RANGE = 10000): ");

    do
    {
        test = scanf("%4u %5u", &num1, &num2);
        fflush(stdin);
    }while((num2 - num1) > 10000 || test != 2);

    printf("The prime numbers of the range %u - %u are...\n\n", num1, num2);

    for(j = num1; j <= num2; ++j)
    {
        for(i = j; i > 0; --i)
        {
            if((j % i)== 0) isprime++;
        }

        if(isprime == 2){ printf("%4u ", j); count++; }
        isprime = 0;
    }
    printf("\n\nPrime numbers count: %d\n", count);

  getchar();
  return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se meter por exemplo 200 300 ele diz que nao posso por numeros negativos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tenta outra vez. Lol. Enganei-me a postar o código.

Já está corrigido.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se puserem números negativos ele não dá números primos... Aparece lá aquele número enorme no lugar do número negativo porque o tipo é unsigned int.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Salvo erro os números primos são apenas positivos.

Já agora, podes optimizar o teu código, não precisas de verificar todas as combinações até zero. Um número é primo se não existirem divisores até à sua raiz.

Por exemplo, 15, à partida falha logo no 3, mas basta-te comparar até 4 (3,8729). Logo, recomendava-te uma verificação com iteração crescente e não decrescente. Aliás, se for par falha logo no 2, imagina que o valor dado foi 70, de 70 até a um  valor que o divida..., ainda demora..., agora imagina 700...

abraços, HecKel

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se usasses o crivo de eratosthenes seria bem mais eficiente (a menos que os valores fossem muitos grandes e o intervalo muito pequeno, mas mesmo assim só perdia em memória).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não faço ideia como é que hei de implementar esse algoritmo...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não faço ideia como é que hei de implementar esse algoritmo... :dontgetit:

http://www.upgaming-hq.com/cd_ioi_05/manual/math.html

mesmo essa versão ainda podia ser mais optimizada...

Não pode sempre?..

Temos simplesmente que encontrar um ponto de equilíbrio.

mas trata-se de uma optimização que foi usada num local e não foi usada noutro (a da raíz quadrada), por isso é que referi.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Realmente o j podia começar em i*i, mas essa optimização é mais complicada de se perceber o porquê do que a outra..

Bem, já tens aí um exemplo do crivo tsenart

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora