- 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.
//java solution with comments
//hope it helps
package ccdec20;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class GBPrimes {
public static void main(String[] args)throws Exception
{
//importing io functions
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st= new StringTokenizer(br.readLine());
//this is number of test cases
int tc=Integer.parseInt(st.nextToken());
//here we store all numbers if prime[i] = 1 then not prime
int primes[]=new int[1000000+2];
primes[0]=1;
primes[1]=1;
//set all multiples of 2 to be not prime
for (int j = 4; j < primes.length; j+=2) {
primes[j]=1;
}
//checking using 3 to sqrt max limit numbers(only odd) and setting all multiples to be 1
//ie not prime
//note were checking from square of n e.g for 3 we start from 9 and increment 2*3 ie 6
//small optimization as 9+3(read odd + odd is even which we already have marked as 1)
//so we increment by 2*i and start from i^2
for (int i = 3; i <= 1000; i+=2) {
for (int j = i*i; j < primes.length; j+=(2*i)) {
primes[j]=1;
}
}
//this is precomputation array...we save count
int count[]=new int[1000000+2];
//during first iternation we check if given count[i] wiz b is prime, if is we check two ahead
//and if it is we simple set count of that index as 1
for (int i = 3; i < count.length; i++)
{
if (primes[i]==1)
continue;
if(i+2<count.length)
if (primes[i+2]==0)
count[i+2]=1;
}
//this loop gives sum of all possible answers upto that index
for (int i = 1; i < count.length; i++) {
count[i]=count[i]+count[i-1];
}
//loop for doing coding
while(tc-->0)
{
int n=Integer.parseInt(br.readLine());
out.println(count[n]);
}
out.flush();
}
}
1 Like