Maximum array size

[Jari-Matti Mäkelä]

Deewiant wrote:
> 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.

They might look clean and elegant, but associative arrays are terribly
slow in this particular case. A hash map would be fast, O(1), if all the
primes were already known, but this isn't the case here. A tree
implementation would have O(log n) average complexity and adding keys to
a hash map would be quite suboptimal too (resizing, collisions).

-- 
Jari-Matti