There are N numbers in an array. You will have Q queries. In each query, you can make 2 operations. …
Click here to read the complete problem statement.
If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.
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)
CLE for Sieve of Eratosthenes solution (https://toph.co/s/648460).
@hjr265 Bhaiya, please increase the CPU limit for Python.
Done. Give it a try now.
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! 
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=node2;
int right=node2+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=node2;
int right=node2+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 = node2;
int right = node2+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?