Maximum array size

[Deewiant]

Ivan Kazmenko wrote:
> Secondly, for any number N, say, 1 <= N <= 100_000_000, I need to have a
> fast way to check whether it is prime.

Sounds to me like you want an associative array. I.e:

bool[int] primes;

primes[769] = true;

if (769 in primes) {
	...
} else {
	...
}

The only annoyance with this is that you might as well set primes[769] to false,
as you don't care about the value, only whether the key exists.