Deepak and primes 2 test cases not passed

#1

my code
https://ide.codingblocks.com/s/40984

question link
https://hack.codingblocks.com/contests/c/512/700

#2

Hey Jai, you can take the max size of an array 10^8 only (the reason for code is not giving any output on online ide). One more thing is try to optimize you solution.

#3

i dont know how to optimize it
please guide me …

#4

please reply…

#5

my code
https://ide.codingblocks.com/s/41196

questn link
https://hack.codingblocks.com/contests/c/512/700

I AM NOT ABLE TO FIND NTH PRIME NUMBER FOR N>=2000
PLEASE TELL ME WHAT TO DO OR GIVE ME AN EXAMPLE OF FURTHER OPTIMIZED CODE
AND A LITTLE EXPLANATION HOW THE OPTIMIZATION WORKS WOULD BE APPRECIATED

#6

please reply…

#7

i have further optimized my code but somehow am not able to get nth prime for n>2000000
https://ide.codingblocks.com/s/41653

MY CODE IS NOT ABLE TO PASS LAST 2 TEST CASES
PLEASE help me improvise my code

#8

try by Initializing j=i*i in line 36 and try to remove all the extra for loops, in line 16 and 21

#9

i did that and still not able to print prime above 3000000
https://ide.codingblocks.com/s/41708

PLEASE HELP

#10

you should declare your array of primes as boolean .
You cannot declare a array of 10^8 size having long long int datatype.
make it global too.

#11

OK
AND
CAN YOU PLEASE TELL ME THE SIGNIFICANCE OF DECLARING IT AS BOOLEAN
AND
AS A GLOBAL VARIABLE

#12

I DID THAT BUT ITS NOT WORKING ABOVE 200000

CAN U PLEASE EDIT MY CODE SO THAT IT WORKS AND I WILL LEARN ABOUT MY MISTAKES FROM THAT

QN LINK:
https://hack.codingblocks.com/contests/c/512/700
my code:
https://ide.codingblocks.com/s/41764

#13

#include
#include<bits/stdc++.h>
#define lli long long
using namespace std;
vector < bool > primes(100000001,true);
long long int arr[5000001];

int main() {
lli n;
cin>>n;
lli j=0,k=1;
lli i;

k=1;
//cout<<primes[7]<<"\n\n\n";
for(i=2;i<=100000000;i=i+1){

    if(primes[i]==true){
        arr[k]=i;

		j=2*i;
		if(k==n)
        {
            cout<<arr[k];
            break;
        }

		k++;


        while(j<100000000){

            //cout<<j<<" ";
            primes[j]=false;
            j=j+i;
        }

    }

}

}

1 Like
#14

bhaiya
IN THE ABOVE CODE
declaring primes array as a vector gives output for very large numbers like 5000000
but declaring primes array via int datatype doesnt

WHY IS IT SO ??

#15

Because size of Boolean is 1 byte and size of int is 4 byte.
Let say in your system , you can make a contiguous memory of 10^8 byte.
Max feasible size of Boolean array= 10^8/1=10^8 byte
whereas feasible max size of int array =10^8/4 byte.
So, it is necessary to create a Boolean array here rather than int array.
IMPORTANT TIP
if your code can work on Boolean array never create a integer array for it.

Hit like if u get it :stuck_out_tongue:

2 Likes
#16

IN THIS NEW QUESTION THAT IS BASED ON THE SAME THEORY I.E SIEVE OF PRIMES
I AM GETTING 2 WRONG ANSWERS ON SUBMISSION
my code
https://ide.codingblocks.com/s/41841

qn link
https://hack.codingblocks.com/contests/c/512/760

CAN U PLEASE HELP ME PASS THOSE 2 CASES

#17

This is not a question of sieve…
This is a question of Segmented Sieve.
First of all try to learn Segmented Sieve and then apply it to this question.

Hit like if u get it

#18

Hey,
Why do not you share all your important tips once and for all! :stuck_out_tongue: btw Thank you so much for your IMPORTANT TIP.