Deepak and Primes problem

#1

https://ide.codingblocks.com/#/s/28160
https://hack.codingblocks.com/dcb/p/700
2/6 test case passed where is the problem ?

#2

a loop till 1000, this is the error actually. n<=5000000, and we want nth prime. So loop till 1000 wont give correct answer for large n. Loop must be till 10^7 atleast, but this will lead to Time Limit Exceed. So try Sieve approach.

#3

will you please help me I am not getting that kind of approach.

#4

https://ide.codingblocks.com/#/s/28336

My approach using sieve. Mark primes till T=10^8 in Tlog(logT)) time, and then use it for getting the answer.

1 Like
#5

https://ide.codingblocks.com/s/44760
If i comment out Line 18, it shows runtime error. Otherwise it gives correct answer.
Why is this ? Pls explain

#6

Hey Akshay, the run time error is not because of line:18 cout statement. Actually in this problem you are supposed to calculate Nth prime no. and N can be or range 5000000 and therefore, Nth prime no. will be of range 100000005, but you have have taken the vector of size 10000000 only which will results in the infinite for loop as count will not become equal to N and loop will never break.

#7

https://ide.codingblocks.com/s/44851
I have changed the vector size to 10^8, but the problem still persists.
Commenting that cout statement leads to a run time error.
And not only for large numbers, this is happening even for inputs as small as 5.

#8

Hey Akshay, declare the vector globally it will work.

#9

Oh yes thank you, It worked !
But I am just curious…

  • How did declaring the vector globally affect the run time of the program ? As it is there was only one function using the vector (the main function) so how did declaring it globally help ? Where all can this technique can be used ?

  • Moreover, how was that cout statement related to this ? Why did commenting that specific line cause a run time error? Is it something related to the compiler ?

If you could please elaborately explain the above ?

#10

Hey, actually when you have declared that array in function it was created in stack memory and when you were printing something compiler got some time and releases some memory which helped in processing and printing the output.
Its resolved by creating the array globally because the global arrays are created in heap memory.

1 Like
#12

I am not able to open any of the code snippets link shared in the chat above :thinking:
Still unable to run my code, could anyone help in sharing the code snippet?