problema de buffer overflow

ubutex
(usa Outra)

Enviado em 02/05/2013 - 15:21h

to resolvendo um exercício e consegui reponde a maior parte dele mas na hora de multiplicar e mostra resultado ele sempre sai -1906577083 pesquisando na internet concluir q resultado extrapola o limite guardada pelas variáveis inteiras, mas se num for isso mesmo assim me ajudem 2 dias sem sair de casa resolvendo tal questão já to que num aguento.
A questão pede ->"Faça um programa que calcule e mostre o produto dos números primos entre 92 e 1.478".
Segue código abaixo.


#include<stdio.h>

#define num 1478

main(){

int i,j,u=1;
int vezes[num];


for(i=2;i<=num;i++)
vezes[i]=1;

for(i=2;i<=num;i++)
if(vezes[i])


for(j=i;j*i<=num;j++)
vezes[j*i]=0;


for(i=92;i<=num;i++){
if(vezes[i]==1){
printf("%d|", i);
u=u*i;
}
}
printf("\n%d\n", u);
}

uilianries
(usa Linux Mint)

Enviado em 02/05/2013 - 15:47h

Nesse link tem uma rotina pra testar se é primo, use:

http://stackoverflow.com/questions/5281779/c-how-to-test-easily-if-it-is-prime-number

Use laço como este:

int liCount = 92;
//Realiza loop de 92 ate 1478
for ( ; liCount <= 1478 ; liCount++ )
{
    //Testa se numero eh primo
    if ( is_prime( liCount ) )
    {
        printf("O numero %d eh primo.\n", liCount);
    }
}
 

Algumas observações da tua postagem:

- Melhore a identação, isso ajuda a manter um código claro
- De nome para as variáveis de acordo com a funcionalidade, i,j,x, var são péssimos nomes.

Abraço.

paulo1205
(usa Ubuntu)

Enviado em 02/05/2013 - 16:33h

Em primeiro lugar, ao postar código no VoL, coloque-o entre as tags [code] e [/code]. Do jeto como você fez, o código ficou muito ruim de ler, e o índice [i] aplicado ao array foi confundido com o marcador do fórum que faz com que o texto fique em itálicos.

Felizmente, aqui no VoL você pode editar a postagem que já fez, permitindo-lhe colocar nela as referidas tags. Isso facilitará a contribuição de outras pessoas, que poderão ler o código com mais clareza.

Um erro básico no qual você incorreu foi esquecer que um array com N elementos usa, em C e C++, índices que vão de 0 a N-1. Eu vi que você declara um array com num elementos e tem um loop em que o índice (i) chega até o valor de num, o que significa que você extrapola em um elemento o tamanho do array.

A forma mais fácil de você corrigir isso é declarar o array com tamanho num+1, sem mexer no resto do programa.

Outro ponto de atenção para você é que o produto de todos os primos compreendidos entre 92 e 1478 certamente excede o tamanho máximo de uma variável do tipo int. Logo, a sua multiplicação pelos fatores primos vai provocar overflow do valor de u, deixando-o com um valor que em nada se parecerá com o que você possivelmente gostaria de encontrar.

Na verdade, só de curiosidade, eu peguei de um site uma tabela de números primos e vi que o produto em questão gera um número com 582 algarismos -- muito maior do que o que se consegue armazenar com unsigned int, unsigned long ou unsigned long long, e maior mesmo do que os limites de float e double. Num PC com GCC (mas não com Visual C++!), long double conseguiria guardar o número, mas com um enorme erro de arredondamento, pois ele só tem 64 bits para a mantissa, ao passo que o valor exato requereria 1936 bits para ser guardado.

Se você precisar do valor exato, talvez você queira usar GMP ou outra biblioteca de bignums (corruptela de big numbers). Se não quiser ou não puder usar bibliotecas externas, talvez a melhor saída seja trabalhar com os números como strings de dígitos, criando as suas próprias rotinas para as operações de soma e multiplicação.

paulo1205
(usa Ubuntu)

Enviado em 02/05/2013 - 16:40h

Sua sugestão é pior (mais ineficiente) do que o que ele fez.

uilianries
(usa Linux Mint)

Enviado em 02/05/2013 - 16:44h

Eu sei, mas não é pra uma questão de complexidade e sim só fim didático.

ubutex
(usa Outra)

Enviado em 02/05/2013 - 17:01h

Obrigado pela ajuda quando tiver tempo vou dar olhada no link valeu.
Valeu também pela dicas de como posta os códigos e pelo boa explicação sobre o erro paulo1205 "melhor que minha professora" e procura saber melhor sobre GMP e biblioteca bignum.

;-) atc.

paulo1205
(usa Ubuntu)

Enviado em 02/05/2013 - 17:15h

Nem eu estou falando de complexidade. Ele implementou um crivo de Eratóstenes completo, que é (mesmo sendo O(n·log(log(n))) em número de instruções e O(n) em consumo de memória) *o* algortimo mais eficiente para a identificação vários de primos de uma vez.

A única desvantagem aparente do que ele fez em relação ao que você mostrou é consumir espaço numa tabela de primos já identificados. Se ele quisesse testar a primalidade de apenas um número, isso seria possivelmente ruim, mas ele *quer* uma tabela, porque ele vai ter mesmo de pegar todos os primos de uma faixa. E certamente ele perderá menos tempo fazendo um crivo do que computando uma série de divisões (operações caras!) por fatores que podem, eles mesmos, não ser sequer primos.

Assim sendo, não vejo esse valor didático de que você fala. Didático é fazer o que tem de ser feito, não o deixar "bonitinho" para um caso particular que é diferente do que se tem em mãos.