Task

[algmaster]

Hi, I'd like you to help me with my school task. I've got some code, but it's too slow. Here it is:

#include <iostream>
using namespace std;

bool T[1000000];

int main()
{
int x;
cin >> x;
int p, n;

for (int g=0; g<x; ++g)
{
cin>>p>>n;
int ile=0;


for (int i=2; i*i<n; ++i)
{
if (T[i]==0)
for (int j=2*i; j<=n; j+=i)
{
T[j]=1;
}
}

for (int i=p; i<=n; ++i)
if (T[i]==0)
ile++;
cout << ile;
}
return 0;
}

Thanks for help!

[lastchance]

Well, it looks vaguely like a Sieve of Eratosthenes for counting the primes between p and n. (Not easy to tell - you need to use code tags).

It doesn't look that slow. The only suggestions I would have are that
you don't put your stack in jeopardy with an array that size, that you initialise your array (to all zeros) (EDIT - I'm wrong; see @jlb's post)
and you don't do the unnecessary (and slow) cout << ile every time: just output it at the end. (EDIT - also wrong - but in my defence I couldn't work out where the loops were without indentation!)

[jlb]

The only suggestions I would have are that you don't put your stack in jeopardy with an array that size, that you initialise your array (to all zeros)

Since the array is a global variable, it is on the heap not the stack, and it is also default initialized.

[jonnin]

since you said school task..
-> many students do not yet grasp release vs debug builds. The code could seem slow because you put debug crap in the executable, strip that out with compiler flags or project settings.
-> vector<bool> can be (and usually is) optimized better than an array of bool. all you have to change is include <vector> and then say vector<bool> T(1000000) -- it should be almost 8 times less memory, which in turn will have a number of good effects that I don't care to go into right now.

if statements *can* (I hate that, but for reasons, it varies) be slower than not having if statements for simple things.
if (T[i]==0)
ile++;
MAY run faster if you ALWAYS execute a statement rather than try to jump over it.
that looks like
ile += t[i]==0; //adds 0 for false, 1 for true.
test it to see which is faster if you like.

[lastchance]

Ah, I see!

You actually do a number of trials (x of them).

And you create a separate sieve for EACH of them!

But you only need to create ONE sieve (based on the biggest n, say). Then you can flick through it for each pair (p,n) at your leisure. Better still, create from it an array containing the cumulative number of primes up to any integer N, F[N]. Then the number of primes between p and n inclusive is F[n] - F[p] + (!T[p]).

[dhayden]

When posting, please include (1) the problem you're trying to solve and (2) how your code works. It's hard to figure these out from the code alone.

This code computes the primes from 2 to 1,000,000 very fast. If it's too slow for the input you're given, then try computing all the primes from 2 to 1,000,000 before you read any input. Then you can just fly through the for (int i = p; i <= n; ++i) loop and print the results. If that's still too slow then you could create a second array int P[1000000] where P[x] is the number of primes less than x. Once you pre-compute this, the number of primes from p to n is P[n+1] - P[p].

[George P]

About using code (and other) tags:

PLEASE learn to use code tags, they make reading and commenting on source code MUCH easier.

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

HINT: you can edit your post and add code tags.

Some formatting & indentation would not hurt either

[seeplus]

As formatted:

#include <iostream>
using namespace std;

bool T[1000000];

int main() {
	int x;

	cin >> x;

	int p, n;

	for (int g = 0; g < x; ++g) {
		cin >> p >> n;

		int ile = 0;

		for (int i = 2; i * i < n; ++i) {
			if (T[i] == 0)
				for (int j = 2 * i; j <= n; j += i) {
					T[j] = 1;
				}
		}

		for (int i = p; i <= n; ++i)
			if (T[i] == 0)
				ile++;

		cout << ile;
	}

	return 0;
}

[TheIdeasMan]

I object to T being used as an identifier: One day when one writes template code this will be hell confusing, as T is a very common template parameter.

[lastchance]

#include <iostream>
using namespace std;

const int MAX = 1000000;
bool T[1+MAX]{};     // false -> prime, true -> composite
int F[1+MAX]{};      // F[N] = number of primes up to and including N

int main()
{
   // Set up sieve  
   T[0] = T[1] = true;
   for ( int i = 2; i * i <= MAX; i++ )
   {
     if ( !T[i] )
     {
        for ( int j = 2 * i; j <= MAX; j += i ) T[j] = true;
     }
   }
    

   // Set up cumulative sum F[N]
   for ( int i = 2; i <= MAX; i++ ) F[i] = F[i-1] + ( !T[i] );


   // Now do trials
   int x;
   cin >> x;

   while ( x-- )
   {
      int p, n;
      cin >> p >> n;
      cout << F[n] - F[p] + ( !T[p] ) << '\n';
   }
}

The sieve could be improved a bit (separate even/odd for starters) but it's not worth it here.

[algmaster]

Thanks! It works. Yeah, the problem with my code was that I didn't make a prefix sum of my T, and I had to do it every time I was getting new numbers. That's why it was slow. Now it works perfectly:)