Problema numere10 de pe campion [variabile globale]

Buna ziua! Intalnesc o eroare la problema numere10 de pe campion,aceasta fiind " Killed by signal: 9 ".
Ce inseamna?
Tin sa precizez ca daca rulez programul folosind datele din exemplu, rezultatul e corect.
Link : http://campion.edu.r...on=view&id=1383
Sursa mea este :

#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("numere10.in");
ofstream fout("numere10.out");
int n,a,i,j,prim[1000001],d,nr,x;
void ciur(int x)
{
int di,m;
prim[1]=0;
for (di = 2; di <= x; di++)
prim[di] = 1;
for (di = 2; di <= x; di++)
	 if ( prim[di] == 1 )
		 for (m = 2 * di; m <= x; m += di)
		 prim[m] = 0;
}
int main()
{
fin>>n;
ciur(1000000);
for( i=1; i<=n; i++)
{
	 fin>>a;
	 if( prim[a] == 0 )
	 for( d=2; d<=sqrt(a); d++)
		 if( a%d==0 && prim[d]==1 && prim[a/d]==1 )
		 {
			 nr++;
			 break;
		 }
}
fout<<nr;
fin.close();
fout.close();
return 0;
}

Iar ideea mea a fost ca pentru fiecare număr a dintre cele n, se va verifica proprietatea de număr “aproape prim”, astfel:
– caut primul divizor d al lui a care este număr prim
– se verifică dacă a/d este număr prim. Dacă da, am găsit un număr apropae prim
Multumesc anticipat!

Edited by Quaintej, 15 January 2017 - 17:00.

Si cu memoria ce ai avut ?

int prim[1000001]

La ce va referiti mai exact?

Quote

de ce ai un sir de 1000000 de numere si nu 10000 ?

vectorul prim ma ajuta sa verific daca un numar a este prim sau nu, iar cum numarul citit a este cuprins între 1 şi 1000000, am considerat ca am nevoie de 1000000 de valori de 0 sau 1 in vectorul prim.
Nu retin numerele citite in niciun vector, nu am considerat ca are rost sa ocup memorie pentru ele.
Totusi, am observat ca daca modific de la 1000000 la 10000 primesc 10 puncte si in rest wrong answer.

Trecand peste implementarea nereusita a faimosului ciur,
citeste - https://oeis.org/A001358 -

tu oricum ocupi memorie cand declari "vectorul" ala de un milion de elemente

Edited by MarianG, 15 January 2017 - 19:38.

Cum as putea sa imi imbunatatesc ciurul?
Nu am facut multe probleme cu ajutorul lui si sunt cam pe langa.

Explica ce faci cu functia ciur, apoi ce face acel for( d=2; d<=sqrt(a); d++)

Vectorul tau e prea mare pentru stiva.

1000001 intregi  = 4 000 000 bytes

1000001 char (ca doar nu vrei mai mult decat 0/1) / 2 (n-o sa ai numar mai mare de 500.000 de verificat daca-i prim) = 500.001 bytes (8x mai putin)

Daca te folosesti de operatii pe biti mai poti imparti la inca 8 totul, cu pretul unor calcule.

Mai scapi apoi si de sqrt ca-i lent si-l apelezi prea des, si mai mult ca sigur te incadrezi in timp

Si sa nu uit, cred ca ti-am repatat pe fiecare topic: RENUNTA LA VARIABILE GLOBALE

#include <fstream>

void populateSieve(unsigned char* items, int maxValue)
{
	items[0] = items[1] = 0;
	for (int i = 2; i < maxValue; ++i)
	{
		items[i] = 1;
		if (items[i] == 1)
		{
			for (int multiple = 2 * i; multiple < maxValue; multiple += i)
				items[multiple] = 0;
		}
	}
}

int main()
{
	std::ifstream in("numere10.in");

	int numberOfItems;
	in >> numberOfItems;

	unsigned char isPrime[500001];
	populateSieve(isPrime, sizeof(isPrime) / sizeof(isPrime[0]));

	int result = 0;

	for (int i = 1; i < numberOfItems; ++i)
	{
		int number;
		in >> number;

		if (isPrime[number] == 0)
		{			
			for (int divider = 2; divider * divider <= number; ++divider)
			{				
				if (number % divider == 0 && isPrime[divider] && isPrime[number / divider])
				{
					++result;
					break;
				}
			}
		}
	}
	std::ofstream out("numere10.out");
	out << result;
	return 0;
}

Edited by dani.user, 20 January 2017 - 22:51.

dani.user, on 20 ianuarie 2017 - 19:35, said:

Ce inseamna?
Ma refer, de ce multiple merge pana la i, cand el incepe cu valoarea 2*i?

Edited by Quaintej, 20 January 2017 - 21:11.

Am corectat