2

Meu problema diz pra somar os primos num intervalo dado pelo usuário, inclusive os intervalos se esses forem primos. Exemplo:

  • ENTRADA: 2 e 10

  • SAÍDA: 17

Consegui fazer isso:

#include <stdio.h>

int main()
{
    int numI, numF, primos = 0;

    scanf("%d %d", &numI, &numF);

    int i;
    for(i = 0 ;numI <= numF; i++){
        if((numI%2 == 0) && (numF%2 == 0))
            primos += i;
    }
    printf("%d", primos);
    return 0;
}

Porém não está mostrando nada após as duas entradas.

1
  • 1
    for(i = 0 ;numI <= numF; i++) - o for vai executar enquanto numI for menor que numF. Como os valores deles são 2 e 10 e nunca são mudados, você criou um loop infinito (nunca sai do for).
    – hkotsubo
    29/06/2018 às 23:33

4 Respostas 4

8

Podemos atacar a questão com um pouco mais de matemática, para então podermos usar outros conceitos de programação. Nesta daqui, vamos abusar do fato de funções puras poderem sofrer memoização.

Resumindo:

  • função pura: dada uma função pura f, se você passar o argumento a, então o valor de f(a) é sempre o mesmo; diz-se de funções que não necessitam de efeitos colaterais
  • memoização: aprendizado na maneira mais simples possível; se eu sei que f(a) = b após fazer una computação pesada, então da próxima vez que me for pedido f(a), retorno b sem computar quase nada; normalmente não é considerado memoização um pré-processamento

Estamos falando aqui da função pura soma_primos_em_intervalo_fechado(início, fim). Porém, o domínio dessa função é grande (na ordem de o(n^2), sendo n a maior entrada possível). Então, essa função não me interessa memoizar.

Porém, essa função pode ser decomposta em uma subtração de uma função pura para dois argumentos distintos:

soma_primos_em_intervalo_fechado(início, fim):
    acumulado_primos_desde_0(fim) - acumulado_primos_desde_0(início - 1)

Vou ficar devendo a demonstração, mas ela é fácil

Então, essa outra função pura tem domínio da ordem de o(n), já é sujeito a memoização. Então, agora nosso problema é apenas definir e escrever essa função acumulado_primos_desde_0(n), usando memoização para otimizar eventuais consultas repetidas.

Essa função vai retornar a soma de todos os números primos até o valor positivo n. Então, se n não é primo, acumulado_primos_desde_0(n) = acumulado_primos_desde_0(n-1). Entretanto, se n for primo, então temos que acumulado_primos_desde_0(n) = n + acumulado_primos_desde_0(n-1).

Assim, podemos definir a função dessa maneira:

acumulado_primos_desde_0(n):
    0, se n <= 0 # caso de falha/caso base
    acumulado_primos_desde_0(n-1), se n não for primo
    n + acumulado_primos_desde_0(n-1), se n for primo 

Como nunca se insere valores negativos nessa função, eu tenho certeza que, para qualquer valor, acumulado_primos_desde_0(n) >= 0. Então posso inicializar meu vetor de memoização com -1 que, como eu garanto que não pertence ao contra-domínio, então significa que meu cache não está carregado com um valor válido, portanto devo fazer a computação pesada.

A definição da função, usando a memoização da maneira mais eficiente que eu consigo imaginar, ficaria assim:

int cache[]; // magicamente inicializou com -1
int acumulado_primos_desde_0(int n) {
  if (cache[n] != -1) {
    return 0;
  }

  if (n <= 0) {
    return 0;
  } else {
   return cache[n] = (eh_primo(n)? n: 0) + acumulado_primos_desde(n-1);
  }
}

Pegue sua versão favorita de detecção de primabilidade, como as opções da resposta do @Lacobus.

Note que o valor do cache é sempre atualizado após um cache miss (exceto parâmetros não-positivos). Portanto, dado a sua variante favorita de eh_primo, as seguintes funções tratam o problema:

int cache[]; // magicamente inicializou com -1
int acumulado_primos_desde_0(int n) {
  if (cache[n] != -1) {
    return 0;
  }

  if (n <= 0) {
    return 0;
  } else {
   return cache[n] = (eh_primo(n)? n: 0) + acumulado_primos_desde(n-1);
  }
}

int soma_primos_intervalo_fechado(int ini, int fim) {
  return acumulado_primos_desde_0(fim) - acumulado_primos_desde_0(ini-1);
}
5

Estava vendo seu código:

#include <stdio.h>

int main()
{
    int numI, numF, primos = 0;

    scanf("%d %d", &numI, &numF);

    int i;
    for(i = 0 ;numI <= numF; i++){
        if((numI%2 == 0) && (numF%2 == 0))
            primos += i;
    }
    printf("%d", primos);
    return 0;
}

No for(i = 0 ;numI <= numF; i++) o i tem que ser igual a numI que no caso seria 2. Exemplo:

for(i = numI ; i< numF; i++)

Sabe-se que números primos são unicamente divisíveis por 1 e por ele mesmo, então:

Aqui if((numI%2 == 0) && (numF%2 == 0)) você só está testando se o número inicial e o final são divisíveis por 2, por isso está incorreto.

Como fazer?

Dentro do primeiro for acrescente outro for assim:

for(j=1;j<i;j++)...

Após criar esse laço você vai comparar o i que no caso é o seu número (que está sendo percorrido do início ao fim) com seu j que vai percorrer do 1 até ele mesmo para testar se ele tem mais algum divisor (se tiver não é primo);

Exemplo:

.
.
.
.
int divisor,aux=0;
for(i = numI ; i< numF; i++){
    divisor=0;
    for(j=1;j<=i;j++){
        if(i%j==0)
        {
            divisor++;
        }

    }
       if(divisor==2)
        {
            aux=aux+i;
        }
}
printf("\nA soma dos primos eh:%d",aux);


.
.
.
0
4

Primeiramente, você vai precisar de uma rotina capaz de determinar se um número é primo:

int eh_primo( unsigned int n )
{
    unsigned int i = 0;

    if( n <= 1 )
        return 0;

    if( (n % 2 == 0) && (n > 2) )
        return 0;

    for( i = 3; i < n / 2; i += 2 )
        if( n % i == 0 )
            return 0;

    return 1;
}

Para somar os primos contidos em um determinado intervalo:

int somar_primos( unsigned int inicio, unsigned int fim )
{
    unsigned int i = 0;
    unsigned int soma = 0;

    for( i = inicio; i < fim; i++ )
        if( eh_primo(i) )
            soma += i;

    return soma;
}

Testando:

int main( void )
{
    unsigned int numI, numF;
    scanf("%d %d", &numI, &numF);
    printf( "%d\n", somar_primos( numI, numF ) );
    return 0;
}

Veja funcionando no Ideone.com

EDIT: Como mencionado pelo @Jefferson Quesado, a função para determinar se um número é primo pode ter sua busca otimizada pela sua raiz quadrada, veja:

int eh_primo( unsigned int n )
{
    unsigned int i = 0;

    if( n <= 1 )
        return 0;

    for( i = 2; i * i <= n; i++ )
        if( n % i == 0 )
            return 0;

    return 1;
}

Veja Funcionando no Ideone.com

2
  • 1
    O segundo if dentro do eh_primo poderia ser simplificado para if (n % 2 == 0) return n == 2;. 30/06/2018 às 0:16
  • 2
    @VictorStafusa vejo elegância em suas palavras, mas infelizmente não vejo uma otimização de fato; iria poupar apenas a inicialização do laço, uma quantia constante de instruções a menos. Creio que buscar até que i*i <= n reduz pela raiz quadrada da busca. 30/06/2018 às 0:54
2

Podemos atacar a questão com um pouco mais de matemática, para então podermos usar outros conceitos de programação. Nesta aqui, vamos aproveitar o fato de que é possível (e eficiente) pré-computar os primos. Um pouco de pré-processamento em um conjunto inicial pode tornar muito mais rápida uma computação futura, ainda mais quando ela é feita repetidas vezes.

Normalmente, em questões de programação competitiva, o programa roda uma única vez e é testado contra uma gama de entradas possíveis. Um exemplo disso é o modelo da Maratona de Programação ACM. A OBI, na minha lembrança, já foi assim também, porém por um tempo ela mudou a abordagem para que cada execução do programa seja um por entrada; então, assim, tem-se que o programa seria executado 15 vezes se fossem 15 casos de testes.

Para fazer esse pré-processamento, vou usar um algoritmo conhecido desde a época dos antigos gregos: o crivo de Eratóstenes.

Ele começa com uma lista booleana. A priori, todo número tem o potencial de ser primo, porém, ao se achar um número primo de verdade, todos os múltiplos dele devem ser marcados como não-primo. Você pode otimizar a execução dele para diminuir a memória pela metade, a dispêndio de um pouco a mais de cálculo (mais umas 3, 4 operações aritméticas por acesso a posição no vetor). Você também pode otimizar para, para cada primo encontrado, fazer apenas o(n/p - p) operações de "anulação de potencial de primo". Veja mais detalhes do algoritmo nesta resposta.

Não me recordo o tempo de execução do crivo, mas ela é algo maior que linear e menor do que quadrática. E tem a vantagem de só se executar uma única vez e se pode guardar os resultados para sempre.

O "retorno" dessa função é uma lista com os primos existentes, e o argumento é ou o número de primos desejado (resposta do Anderson Carlos Woss) ou o tamanho máximo do maior primo. Eu acho que para o seu caso devemos passar 10000 (dez mil) que devemos ter alguma margem de segurança. Eu não posso afirmar com certeza, você não pôs as restrições de entrada para o seu problema.

Vamos assumir que a variável preenchida com os primos obtidos pelo crivo de Eratóstenes se chame primos, e a quantidade total de primos achada se chame qnt_primos. Se se deseja somar todos os primos no intervalo fechado [numI, numF], então só fazer o seguinte:

int i;
int soma = 0;
int numero_iterado;

// ... faz os primos, faz as leituras necessárias

for (i = 0; i < qnt_primos; i++) {
  numero_iterado = primos[i];

  if (numero_iterado < numI) {
    continue; // volte para o começo do laço, ainda nem cheguei no mínimo 
  } else if (numero_iterado > numF) {
    break; // achei um primo que vai além do valor final, posso parar
  }
  soma += numero_iterado; // primo no intervalo, deve somar
}
printf("%d", soma);

Se quiser, é ainda fácil considerar um algoritmo de busca binária para achar o índice j do menor primo disponível, que é primos[j] <= numI.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .