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.

@fahmid07
I think this should help:

1 Like

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 image Toph Community, @trojan_attack! :wave:t5:

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! :grinning:

1 Like

Run time error, unable to find what’s wrong with this code :disappointed:

#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=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=node2;
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 = node2;
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

Please Help me finding out my faults .
https://toph.co/s/720569