[need help] PRIME1 with Sieve of Erathostenes

[fdominik1994]

Hello!

I'm getting TLE error. What is the problem? I tried to replace cin and cout with scanf and printf, but the result is the same. Is this method too slow for spoj?
Here is my code:

#include<stdio.h>
#include<vector>
int main()
{
	int t;
	scanf("%d", &t);
	for (int main_i = 0; main_i < t; main_i++)
	{
		typedef unsigned long ul;
		ul m, n;
		scanf("%lu%lu", &m, &n);
		std::vector<bool>sieve(n+1, true);
		for (ul i = 2; i <= n; i++)
			if (sieve[i])
				for (ul j = 2; i*j <= n; j++)
					sieve[i*j] = false;
		for (ul i = m; i <= n; i++)
			if (sieve[i])
				printf("%lu\n", i);
		putchar('\n');
	}
	return 0;
}

Thank for your answers!

[leppyr64]

for (ul i = 2; i <= n; i++)

n can be as large as 10^9. You then have another loop inside of this one. This will take an incredibly long time to run.

Question: Do you really need to calculate the list of primes from 1 to N for every test case? For example, if we had the following test case:

5
10000 20000
10000 20000
10000 20000
10000 20000
10000 20000

Would you really need to count all the primes from 1 to 20000 every time?

Hint: There is another constraint that you have been given that you can make use of.

[fdominik1994]

I have just done some improvments, but it doesn't enough.

#include<stdio.h>
#include<vector>
typedef unsigned long ul;
int main()
{
   int t;
   scanf("%d", &t);
   for (int main_i = 0; main_i < t; main_i++)
   {
      ul m, n;
      scanf("%lu%lu", &m, &n);
      std::vector<bool>sieve(n+1, true);
      ul m_half=(m>3)?m/2:m;
      for (ul i = 2; i*i <= n; ++i)
     if (sieve[i])
        for (ul j = m_half; i*j <= n; ++j)
           sieve[i*j] = false;

  if(m==2){
    printf("%d\n",2);
    for (ul i = 3; i <= n; i+=2)
         if (sieve[i]){
            printf("%lu\n", i);
         }
  }
  else{
    if(!(m%2))
        ++m;
    for (ul i = m; i <= n; i+=2)
         if (sieve[i]){
            printf("%lu\n", i);
         }
  }
  putchar('\n');
   }
   return 0;
}

After that I rewrited the use of the vector, but I didn't see any improvments, especially with low number input.

#include<stdio.h>
#include<vector>
typedef unsigned long ul;
int main()
{
    std::vector<bool>sieve(1000000000,true);
    ul max_m=2;                                        
	int t;
	scanf("%d", &t);
	for (int main_i = 0; main_i < t; main_i++)
	{
		ul m, n;
		scanf("%lu%lu", &m, &n);
		for (ul i = 2; i*i <= n; i++)
			if (sieve[i]){
				for (ul j = max_m; j <= n/2; j++)
					sieve[i*j] = false;
			}
        if(max_m<m)
            max_m=m;
        for(ul i=m;i<=n;++i)
            if(sieve[i])
                printf("%lu\n",i);
		putchar('\n');
	}
	return 0;
}

Would you like to give me some more advices? Is there any chance to do this with Eratosthenes? Or there are other simplier and faster methods?

[leppyr64]

You need to use the sieve of erastothenes, but not the way you are doing it. You cannot use the sieve to find all primes from 1 to n.
You really need to think about the constraints that were given in the problem statement. Use the small ones to your advantage.

The problem with your code is not with small number input, it's with large number input.

Possibly a helpful question: What is the definition of a prime number?

[fdominik1994]

Prime number is an integer which only can be divided by 1 and by that integer. A number is not prime if it has prime factors.

After some more research I found the solution, the segmented sieving. I think you did speak about this method before, didn't you?

My submit is accepted, but it has 0.70s runtime, the memory usage is good, 2.8Mb. Now I don't know how can I optimize it. Any advice?

Last, but not least thank you very much for your help, without you I couldn't able to solve this.

[leppyr64]

In the years that I have been on this forum I have talked about this problem many times (At least 4 unique users this week) I have probably mentioned segmented sieving a few times, I don't know if I did in this thread though.

I don't usually care about speed. I generally do most of my coding in a competition environment (Google Code Jam, etc) and therefore prefer a solution that is short and easy to understand at a "good enough" complexity. Decreasing execution time usually involves more elaborate solutions (home grown data structures, low-level IO, etc)

Common things that increase speed are:
Avoiding memory allocation - allocate memory once, and then use that for all of the test cases.
Use scanf/printf instead of cin/cout.
Avoid reduntant calculations:

for(int i = 0; i < sqrt(x); i++)

sqrt(x) will be calculated at every iteration of the loop. If x doesn't change within the loop, then store that calculation in another variable.

int z = sqrt(x);
for(int i = 0; i < z; i++)

If you wanted to pm me your code I might be able to point some things out.