Limits: 1s, 256 MB

There are **N** numbers in an array. You will have **Q** queries. In each query, you can make 2 operations. These are:

This is a companion discussion topic for the original entry at https://toph.co/p/easy-prime

Limits: 1s, 256 MB

There are **N** numbers in an array. You will have **Q** queries. In each query, you can make 2 operations. These are:

This is a companion discussion topic for the original entry at https://toph.co/p/easy-prime

You need to figure out something more efficient.

Whatâ€™s wrong with my code??

if the number of query operations is large your code can not pass this time because of time complexity N*N.To pass your code in time you should apply segmented Tree or Binary Index Tree(BIT).

can i do it by seive or segseive? Reply earlier kindly.

use sieve with some modifications!

like donâ€™t save primes just make a bool array and just look upto sqrt(1e7) for primes but mark till 1e7 (though 5e6 works) !

(0.0s solution)

1 Like

CLE for Sieve of Eratosthenes solution (https://toph.co/s/648460).

@hjr265 Bhaiya, please increase the CPU limit for Python.

1 Like

Done. Give it a try now.

1 Like

All indexes are 1-based means?

Welcome to the Toph Community, @trojan_attack!

1-based (array) indexing is a way of numbering the elements of an array such that the first element of the array has an index of 1.

For example, an array `A`

with `n`

items is accessed as `A[1], A[2],..., A[n]`

.

In this problem, indices given/inputted are using the 1-based indexing system.

Hope it helps!

1 Like

Run time error, unable to find whatâ€™s wrong with this code

#include <bits/stdc++.h>

#define mx 200

using namespace std;

bool prime[200] ;

void SieveOfEratosthenes()

{

memset(prime, true, sizeof(prime));

prime[0]=false;

prime[1]=false;

for (int p = 2; p * p <= 200; p++)

{

if (prime[p] == true)

{

for (int i = p * p; i <= 200; i += p)

prime[i] = false;

}

}

}

int arr[mx];

int tree[mx*4];

void init(int node,int b, int e){

if (b==e){

int ma=0;

if(prime[arr[b]]){

ma=1;

}

tree[node]=ma;

return;

}

int mid=(b+e)/2;

int left=node*2;
int right=node*2+1;

init(left,b,mid);

init(right,mid+1,e);

tree[node]=tree[left]+tree[right];

}

int query(int node , int b, int e, int i , int j){

if (i>e || j<b )

return 0;

if (b>=i && e<=j)

return tree[node];

int mid=(b+e)/2;// else

int left=node*2;
int right=node*2+1;

int p1=query(left,b,mid,i,j);

int p2=query(right,mid+1,e,i,j);

return p1+p2;

}

void update(int node, int b, int e, int i, int newvalue){

if (i>e || i<b){

return;

}

if(b >= i && e<=i ){

tree[node]= newvalue;

return;

}

int left = node*2;
int right = node*2+1;

int mid=(b+e)/2;

update(left,b,mid,i,newvalue);

update(right,mid+1,e,i,newvalue);

tree[node]=tree[left] + tree[right];

}

int main()

{

SieveOfEratosthenes();

int t;cin>>t;

for (int i=1; i<=t; i++){

cin>>arr[i];

}

init(1,1,t);

int q;cin>>q;

for(int i=0; i<q;i++){

int d,l,r;cin>>d>>l>>r;

if(d==1){

cout<<query(1,1,t,l,r)<<"\n";

}

else{

int u_val=0;

if(prime[r]){

u_val=1;

}

update(1,1,t,l,u_val);

//for(int j=1; j<=2*t-1; j++){

// cout<<tree[i]<<" â€ś;

// }

//cout<<â€ť\n";

}

}

```
return 0;
```

}

What will be the range of A[i]?

Is it 0<= A[i] <= 1e9 or something else?

1 Like