Is the size of an array limited?

general
, ,
1

Here is link to my code-
http://www.codechef.com/viewsolution/2174509

I guess for inputs like 9999000 10000000, the program didn’t run due to the size limit of the array,
as one “hey” is being printed and the next to the array declaration is not!
Please do help…

1 Like
2

Of course it is, unbounded tape for turing machine is just a theory…

3 Likes
3

@wonder : The actual limits of the problem are till 10^9 , so there is no hope that you can allocate that large an array . For the sizes you are mentioning 10^7 and int declaration would take 40 MB main memory which may be allowed but you have to check system settings for memory available .

5 Likes
4
  • Max Array size varies from system to system. For eg : It is 10^6 in case of local declaration and varies from 10^7 to (2.5)*10^8 in case of global declaration.(My experience).
  • However in this problem , You don’t need to calculate primes upto 10^9 ofcourse(as not possible through array). You need to calculate and cache primes <=Max(sqrt(n)) i.e sqrt(10^9) i.e around <=31622 only.
  • Try solving now. If you face any further problem you can have a look at my solution : http://www.codechef.com/viewsolution/1860904.

Enjoy :slight_smile:

6 Likes
5

hey…i guess the square root wouldn’t be giving the perfect ans(precision)…so how could it be divided by prime number exactly!!! eg- 15.

6

And maybe you can simply iterate all numbers and count the primes using knowledge from MAY contest - Witua and Math. I have to try it :slight_smile:

7

We know pretty well that any number can be factorized into powers of its prime factors. Hence for checking primality of a number we will check its divisibility by all prime numbers <= to its square root . If not a single such factor found then the number is prime ofcourse.

8

@betlista : Not using java version of witmath ofcourse :stuck_out_tongue:

9

Why? There are only 11 numbers to read and slow input is a problem in Java… But maybe you are right, will see :smiley:

10

Good Luck. And post the solution when you are done :slight_smile:

11

hey…why did u took till 31607 and not more than that…
in ur prime number list??

12

Read the explanation again slowly.

13

oops got it thnx…@all

1 Like
14

It’s not a theory, it’s a model.

15

@msasha : Yes, but what betlista is trying to say is,Tm’s are not practically possible as they can even manipulate unbounded set of data and can be used to achieve automaton in minimum number of states.

16

There are two places memory can be allocated:

On the heap (dynamically allocated memory).
The size limit here is a combination of available hardware and the OS’s ability to simulate space by using other devices to temporarily store unused data (i.e. move pages to hard disk).

On the stack (Locally declared variables).
The size limit here is compiler defined (with possible hardware limits). If you read the compiler documentation you can often tweak this size.
Thus if you allocate an array dynamically (the limit is large and described in detail by other posts.

int* a1 = new int[SIZE]; // SIZE limited only by OS/Hardware
Alternatively if the array is allocated on the stack then you are limited by the size of the stack frame. N.B. vectors and other containers have a small presence in the stack but usually the bulk of the data will be on the heap.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame
enjoy :slight_smile:

4 Likes