Code optimization

#1

Hey there!
Can you suggest how I can optimize my code.
It is giving wrong answer for test case 1 and time limit for the second. It works fine on the sample test case.
#include<bits/stdc++.h>
using namespace std;

int main() {

vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(5);
v.push_back(7);
v.push_back(11);
v.push_back(13);
v.push_back(17);
v.push_back(19);

int t;
cin>>t;
t++;

while(t--)
{
	int n;
	cin>>n;

	int ans=0;

	for (int i=0; i<n; i++)
	{
		bool flag= false;
		for (int j=0; j<8; j++)
		{
			if(i % v[j]==0)
			{
				flag=true;
			}
		}

		if (flag==true)
		{
			ans++;
		}
	}
	cout<<ans<<"\n";
}


return 0;

}

#2

This code is wrong. I suggest you correct this code first before moving on to optimization. You have made a mistake in the bruteforce approach.
The for loop must go from 1 to n

for(int i = 1;  i <= n;  i++)

And I also suggest you to initialise the vector using initialiser_list.

vector<int> v = {2, 3, 5, 7, 11, 13, 17, 19};
#3

And for optimisation I give you a hint. The number of numbers between 1 and N divisible by a number P is equal to N / P.

Say you have the array of only first 2 prime numbers. {2, 3}
Number of numbers divisible by 2 be int d2 = N / 2;
Number of numbers divisible by 3 be int d3 = N / 3;

But the answer is not equal to d2 + d3 as now there is some overlapping.

Because now numbers between 1 and N that are divisible by 6 are counted twice.
So we need to subtract those numbers. So,

Number of numbers divisible by 6 be int d6 = N / 6;

So answer for this problem will be d2 + d3 - d6 (int ans = d2 + d3 - d6;).

This was just for 2 and 3, you need to do this for the whole array of {2, 3, 5, 7, 11, 13, 17, 19}.
Please check my code
#4

Well, I don’t think that it is necessary coz I have to divide only with the prime numbers.

#5

I made the changes. It is still giving me the same errors.

#6

what do you think is not necessary ?? I also divided by only prime numbers 2 and 3. Have you read what I have written completely. You will get repetitions in this. And seeing the constraints which are upto 10^18 the solution is only possible in O(1) or O(logn).

#7

What changes have you made, and what errors are you getting. You’ll always get TLE on that code as I already told you.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.