I found all the prime numbers till n and then stored it in arraylist and then checked the given conditions. The answer was coming right but approach gave TLE. What could be the possible reason?
Pls help
Question
Solution
- T <= 10^6
- You are recalculating all primes in every testcase, just do it once outside.
Try fixing these first.
2 Likes
You generate the primes for each test, so it takes O(t \times n \times log log (n)).
You can precalculate the primes in O(n log log (n)) and then answer queries in O(1) per query for a total of O(t + n \times log log (n))
7 Likes
You can simply check the conditions globally and just print the answer in O(1). You are getting TLE as you are precomputing seive for each test case
1 Like
you can think of dp here
after storing primes in arraylist
example n=5and 6
primes {2,3,5}
dp[5]=1;
dp[6]=1;
again for n=7
primes{2,3,5,7}
dp[7]=dp[6]+1;
2 Likes
In your solve function ,to search the numbers the time complexity is n^2 which will not pass the constraints .You could improve your sieve function instead of pushing p in the vector check if p-2 is prime and if true push that into the vector and then in the solve function just use binary search for n and print the value.
https://www.codechef.com/viewsolution/41870699
time complexity of solve fn is O(n).
Can anyone please suggest me edits for not getting TLE, even though I have precomputed the sieve.
But applying binary_search for checking the no c. Please have a look at my code.
This is my code here CodeChef: Practical coding for everyone
yes sry…but still calculating the ans in O(nt +nloglog(n)) will fail the constraints .You could modify it to answer queries in O(1) but answering in O(logn ) should also suffice.
You are building the list of primes for every test case and applying binary search in a loop which will increase your time complexity. See my reply above Prime Tuples Codechef div 3 January Cookoff - #10 by new_coder_12
Yes got my mistake…Thanks
// between a given interval
#include <bits/stdc++.h>
using namespace std;
vector<int > v;
// Function for print prime
// number in given range
void primeInRange(int L, int R)
{
int flag;
// Traverse each number in the
// interval with the help of for loop
for (int i = L; i <= R; i++) {
// Skip 0 and 1 as they are
// niether prime nor composite
if (i == 1 || i == 0)
continue;
// flag variable to tell
// if i is prime or not
flag = 1;
// Iterate to check if i is prime
// or not
for (int j = 2; j <= i / 2; ++j) {
if (i % j == 0) {
flag = 0;
break;
}
}
// flag = 1 means i is prime
// and flag = 0 means i is not prime
if (flag == 1)
v.push_back(i);
}
}
// Driver Code
int main()
{
// Given Range
int t;
cin>>t;
while(t--)
{
int L=1;
int R;
cin>>R;
// Function Call
primeInRange(L, R);
int c=0;
//for(auto x: v)
//cout<<x<<" ";
for(int i=0; i<v.size(); i++)
if(v[i+1]-v[i]==2)
c++;
cout<<c<<endl;
v.clear();
}
return 0;
}
can anybody tell why i am getting TLELet me walk you through the thought process of this problem, It is given that there are 105 test cases and per test n could be as large as 106 at this point you should be alarmed that it’s not wise to do anything in O(n) per test case. Now I am currently not thinking about prime generation but I see that a<b<c for a tuple ( a, b, c ) that is defined as prime tuple, also given that a+b = c now, realize that if a+b=c has to be true for primes a,b,c the only way this happens for a = 2 because it’s the only even prime, had this not been true, then a+b would be even ( as all primes greater than 2 are odd and any of them would sum to an even number ) and there is no even prime greater than 2 so it’s absolutely certain that a = 2, now we need to look for b and c, so do this b = c-2, so I need all tuples of ( 2, c-2, c ) such that c-2 and c should be primes as well, Now All need to know is if c-2 and c are primes are as quickly as possible, and the best I can do is pre-compute them and do O(1) check if c-2 and c are both primes. Now I know for each c is if c-2 and c are both primes so something like primes[c] and primes[c-2] could tell me in constant time if I have a prime tuple ( 2, c-2, c ) and I mark it as true that yes I have a prime tuple ending at c and now I just look how many such tuples I had before this one, all I need to do is add this one to those and I have my answer, that is why I pre-process using sieve that will give me O(nlog(log(n)) before query answer, and to be able to know the number of pairs upto certain n I do prefix sums, ie. prefix[n] gives be number of tuples upto n, So my query time is just O(1) and It makes sense as I have 105 queries or test cases. Hence the solution of sieve + prefix array.
void PrimeTuples(){
ll n = 1000005;
vector<bool>primes(1000005,1);
primes[0] = primes[1] = 0;
for(int i =2;i*i<=n;i++){
if(primes[i]){
for(int j = i*i;j<=n;j+=i){
primes[j] = 0;
}
}
}
vector<ll>prefix(n,0);
for(int i = 5;i<=n;i++){
if(primes[i] and primes[i-2]){
prefix[i] = 1;
}
prefix[i] =prefix[i]+prefix[i-1];
}
int t;
cin>>t;
while(t--){
ll x;
cin>>x;
cout<<prefix[x]<<'\n';
}
}
2 Likes
-
Initialize a precompute array of size 1e6 (10^6) to all zeroes.
-
Generate the primes before processing all test cases using sieve of eratosthenes.
-
Now simply check if numbers i and i-2 are prime for all 1<=i<=1e6. if so, increment preCompute[i] by copying the previous value and incrementing that by 1. Else, simply copy preCompute[i-1] to preCompute[i].
Note that this should be done before processing all test cases.
A small hint: you can start your precomputation process from the number 5, since it is the smallest prime number that can be represented as the sum of two primes.
My Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int preComp[(int) 1e6 + 1] = {0};
void sieve(int n){
bool prime[n+1];
memset(prime,true,sizeof(prime));
for(int p=2;p*p<=n;p++){
if(prime[p] == true){
for(int i=p*p;i<=n;i+=p)
prime[i] = false;
}
}
int c = 5;
preComp[c] = 1;
for(int i=c+1;i<=n;i++){
if(prime[i] && prime[i-2]){
preComp[i] = preComp[i-1] + 1;
}
else{
preComp[i] = preComp[i-1];
}
}
}
int main() {
sieve(1e6);
int t;
cin >> t;
while(t>0){
int n;
cin >> n;
cout<<preComp[n];
cout<<endl;
t--;
}
return 0;
}
@akshay_012 You are doing O(n) check for a prime and for each test case, you do realize that t is as large as 105 so it will blow up to O(t*n) and see that will not pass no matter what.
I gave the thought process below, that should help.
thk dude
see (to all) , u must have to print the each test case in O(1) , so for precomputation there will be two scenarios -
- in N(root(n)) -
bool isPrime(ll x){
for(ll j=2;j<=sqrt(x)+1;j++) {
if(x%j==0) return 0;
}
return 1;
}
vector <ll> answers(2e6+10);
void calcPrime(){
ll cnt = 0;
for(ll i= 3;i<=1e6+10;i++){
if(isPrime(i) && isPrime(i+2)){
cnt++;
}
answers[i+2] = cnt;
}
}
void solve(){
ll n;
cin>>n;
cout<<answers[n]<<endl;
}
int main(){
fastIO
ll t=1;
cin>>t;
calcPrime();
while(t--) {
solve();
}
return 0;
}
2-(using sieve(Nloglogn))
bool prime[MAX+1];
void sieve1(){ //prime or not
for(int i=0;i<=MAX;i++) prime[i]=1;
prime[0]=prime[1]=0;
for(lli i=4;i<=MAX;i+=2) prime[i]=0;
for (int p=3; p<=MAX; p+=2){
if (prime[p] == 1){
for (int i=p*2; i<=MAX; i += p){
prime[i] = 0;
}
}
}
}
int main(){
fastio
sieve1();
lli t=1;
cin>>t;
lli dp[1000001]={0};
FOR(i,2,1000001)
{
if(prime[i+2]and prime[i])
dp[i+2] = 1;
}
FOR(i,1,1000001)
{
dp[i] += dp[i-1];
}
while(t--)
{
lli n;
cin>>n;
print(dp[n]);
}
return 0;
}
what about my approach dude it is able to pass all test case if there t=5,n=10^4
becoz(tle) i don’t know whether it’s correct or not
I have a very nice trick for you suppose we have to calculate tuples till 6 then we have (2,3,5) and if we have 20 we have [(2,3,5),(2,5,7),(2,11,13),(2,17,19)] and now if you look closely you’ll see that for the condition a+b=c to be satisfied one of the a or b must be even prime which is two because " sum of two primes can never be a prime " now you just have to fix 2 and calculate (2+i)th and check it with +2 and find the next number is prime or not , you can do this with Seive of Eratosthenes.