Zadanie cpp liczby pierwsze

Question

Witam, da się to jakoś przyspieszyć? na spoj'u jest zbyt duzy czas kompilacji.

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x=10000;
	bool liczby[x];
	for(int i=0; i<x; i++)
	{
		liczby[i]=true;
	}
	for(int i=2; i<=sqrt(x); i++)
	{
		if(liczby[i]==true)
		{
			for(int j=i+i; j<=x; j=j+i)
			{
				liczby[j]=false;
			}
		}
	}
	liczby[0]=false;
	liczby[1]=false;
	int y; cin>>y;
	for(int i=0; i<y; i++)
	{
		int z; cin>>z;
		if(liczby[z]==true) cout<<"TAK";
		else cout<<"NIE";
		cout<<endl;
	}
}

 

Comments

W linii 15 masz bład, porównanie musi być ostre J<x, inaczej możesz trafić poza tablicę. Co prawda najwyżej o 1 element, pewnie błąd dostępu nie wyskoczy, ale formalnie jest błąd.

Druga nieścisłość w tej samej linii to j = i+i, powinno być i*i. Powinno przyspieszyć.

 

Dla porównania - o ile dobrze pamiętam, podobnie zoptymalizowane sito Erastotenesa, w Pascalu, z użyciem packed array of boolean (kompilator to zrobił na bitach), liczony do 1000000 wykonywał się 15 minut na Odrze 1305.

Problem masz z czasem kompilacji czy wykonania?

Poza powyższą uwagą samo sito chyba masz zoptymalizowane maksymalnie.