Maratonime: Hiperprimos

Oi galere

Estou entrando em uma crise existencial com um problema aqui, o hiperprimos ( https://www.urionlinejudge.com.br/judge/pt/problems/view/1602 ) que já faz mais de 3h30 que eu já deveria ter ido dormir mas continuo empacado nele! Enfim ;)

O meu programa precisa funcionar para todo N até 2.10⁶, então meu vetor de hiperprimos vai até 2.10⁶, pelo que entendi. Pois bem, a partir de ~1047625 ele começa a dar Segmentation fault (curiosidade: com o valor que eu escrevi aqui (1047625), aconteceu de eu compilar e ele funcionar, compilar de novo sem mudar exatamente nada e ele dar segmentation fault, compilar mais uma vez sem mudar nada e funcionar, etc). Já tentei trocar os int por unsigned int ou coisas do gênero mas não está rolando.

Alguma alma caridosa faz ideia do que esta se passando? O problema eh a logica do algoritmo, eu tenho que desenvolver algo que utilize menos memoria? Quando coloco MAX = 1000000 ele funciona bonitinho, talvez se eu criar dois vetores de tamanho 1000000 eh uma saída? Vou tentar amanhã (acabei de ter essa ideia enquanto escrevo mas já estou derrotado pelo exercício :p )

Estou enviando meu código já meio comentado em anexo. Desde já, obrigado (está salvo como .cpp mas está feito em C normal).

1602.cpp

Re: Hiperprimos

by Marcio T. I. Oshiro - Wednesday, 18 March 2015, 2:28 PM

Primeiro, dois vetores com 2 x 10^6 posições cada são muito grandes para serem declarados localmente (dentro de uma função). Eles precisam ser globais. Isso porque, basicamente, os espaços reservados na memória para variáveis locais e variáveis globais são diferentes. Para saber mais sobre isso veja http://www.tenouk.com/ModuleW.html

Mesmo corrigindo isso, seu código tem problemas. Um dos principais motivos para segmentation fault é acessar uma posição inválida de um vetor. Tente conferir todos os acessos à posições de vetores e verifique se os índices estão sempre entre zero e MAX.

Uma última coisa é seu laço de leitura que nunca vai parar. O valor devolvido pelo scanf é o número de "coisas" que ele conseguiu ler (1 se ele ler o valor de N) ou EOF (se chegar no final do arquivo). Mas note que EOF == -1. Logo, a condição do seu while é sempre verdadeira.