1086. Cryptography | Editorial by Complexity

1086. Cryptography | Editorial by Complexity_Cutter

An observation: 15000th prime number is 163841 .

Approach        : We can use sieve function to determine primes form 1 to 163841 . By sieve We can just check, whether a number is prime or not in constant time complexity.
                           And sieve's complexity is  O(√range).  In this problem range is 163841. let an array check_prime[] which stores the info whether  a number is prime or not.
                           Then we will traverse the array check_prime from index 1 to index 163841 and store the primes in an another array. Let the array be primes[]. 
                           Then, in each query we will give the answer in constant complexity.
                           
Time complexity of this solution is: maximum of O(√range) and O(number_of_queries).
Space complexity of this solution  : O(range+number_of_primes_between_the_range)

code :

***sieve=>

short int check_prime[170000];

void sieve(){
    long long int i,j;

check_prime[0]=1;
    check_prime[1]=1;
    check_prime[2]=0;

for(i=2;i*i<=170000; ){
        if(check_prime[i]==0){
            for(j=i;i*j<=170000;j++){
                check_prime[i*j]=1;
            }
        }
        if(i==2)
            i++;
        else
            i+=2;
    }
}

***primes generation
//nop=>number_of_primes

int primes[20000];

for(i=2;i<=170000; ){
        if(check_prime[i]==0){
            primes[nop]=i;
            nop++;
        }
        if(i==2)
            i++;
        else
            i+=2;
        if(nop==15005) 
            break;
    }
    
    
    ***Answer Queries
    //Q=>number of queries
    
    for(i=1;i<=Q;i++){
        scanf("%d",&k);
        printf("%d\n",primes[k]);
    }

1086. Cryptography | Editorial by Complexity_Cutter

Download submission

All caught up!

View submission

Is your resume even shortlisted?