PRIME1, too slow

[rsala004_sof]

What is wrong with my code that it is too slow? (6 seconds exceedED?!?!)
code does what problem statement intends (correctly)

Thanks!

#include <iostream>
#include <vector>
using namespace std;
vector<int> * countPrimes(const int& start,const int& end)
{
vector<int> *p = new vector<int>;
for ( int i = 2 ; i <= end; ++i)
{
	if(i!=1)
	p->push_back(i);
}
//eratosthenes
for( int i = 0; i < p -> size(); ++i)
{
	for(int j = i+1; j < p -> size(); )
	{
		if(p->at(j) % p->at(i) == 0)
		p->erase(p->begin()+j);
		else
		++j;
	}
    if( p->at(i) >= start)
	cout << p->at(i) << endl;
}
cout << endl;
return p;
}
int main()
{
	int trials;
	cin >> trials;
	int *nums = new int[trials*2];
	for(int i = 0; i < trials*2; ++i)
	{
		cin >> nums[i];
	}
    for(int i=0;i<trials*2;i+=2)
{
	countPrimes(nums[i],nums[i+1]);
}
}

[TripleM_sof]

Why would you think that program would run inside 6 seconds? Surely you've tried an input of the maximal size (999900000 1000000000)?

[rsala004_sof]

do you suggest pre-calculating the primes?

[TripleM_sof]

Sorry, I don't give out solutions Just showing why your code is much too slow.

[rsala004_sof]

But just to be certain, i dont have to 'cheat' to solve the problem do i? I dont have to have the primes precompiled do i?

and heres my latest attempt, of course its WAY slow. ( i am seeing that even just checking integer by integer if it is prime would maybe be faster..still not fast enough, i might just scrap this attempt.)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
void countPrimes(const int& start,const int& end)
{
int bound = (int)floor(sqrt((double)end));
vector<int> *p = new vector<int>;
p->push_back(2);
for ( int i = 3 ; i <= end; i+=2)
{
	p->push_back(i);
}
//eratosthenes
for( int i = 1; i < p -> size(); ++i)
{
	if(p->at(i) > bound)
	{
		break;
	}
    for(int j = i+1; j < p -> size(); )
{
	if(p->at(j) % p->at(i) == 0)
	p->erase(p->begin()+j);
	else
	++j;
}
}
for(int i= 0; i < p->size();++i)
	if(p->at(i) >= start)
		cout <<  p->at(i) << endl;
cout << endl;
}
int main()
{
	int trials;
	cin >> trials;
	int *nums = new int[trials*2];
	for(int i = 0; i < trials*2; ++i)
	{
		cin >> nums[i];
	}
    for(int i=0;i<trials*2;i+=2)
{
	countPrimes(nums[i],nums[i+1]);
}
}

[leppyr64]

Can you see anything that you're doing multiple times needlessly?

[rsala004_sof]

well I do see that I am calculating the primes once again for each CASE but even if I enter in a SINGLE case of just (999900000 1000000000) as tripleM suggests, it takes forever to finish (if it even ever does).

Any ideas ?

how can i possibly find the primes between (999900000 1000000000) under 6 seconds? (without PREVIOUSLY knowing the primes between 2 -> sqrt( 1 billion) )

[leppyr64]

Some common hints will be to avoid stl, and avoid cin and cout.

Past that you should ne able to see some obvious points where your program is too slow. Just knowing that it's possible should show you some locations where your method is reducilous.

[guest_on_earthes]

I think that your problem in vectors
Try to use ordinary arrays