try sieve algorithm for spoj problem

[surfersss]

try to solve spoj prime generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

  // sieves.cpp : This file contains the 'main' function. Program execution begins and ends there.
    
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    int main()
    {
    	int  g, h, o;
    	scanf("%d", &o);
    
    	for (int j = 0; j < o; j++) {
    		scanf("%d", &g);
    		scanf("%d", &h);
    
    		long long *l = new long long [h];
    
    
    		l[1] = 1;
    		int i = sqrt(h);
    		for (int k = 2; k <= i; k++) {
    			for (int j = 2; (k*j) < h; j++) {
    				l[k*j] = k * j;
    
    			}
    
    		}
    
    		for (int p = g; p < h; p++)
    		{
    			if (*(l + p) == 0)
    				printf("%d \n", p);
    		}
           delete[]l;
    
    	}
    
    }

i got SIGABRT runtime error
why and how to solve this error? is it because the memory?

[jonnin]

probably. how much ram do you have? You asked for
new long long int[h * sizeof(*l)];

what did you type in for h?

why are you treating new like malloc?
it looks like it should just be new long long[h] to me. That new statement looks very screwy. and long long int isnt correct, its just long long.

why do you have all the C statements and headers? <cmath> is the c++ math.h, for example.

is this using turbo C++? thats a 16(?) or 32 bit compiler, I don't think it can handle more than 2gb memory in one block.

lets stat here: does your program work if you type in 100 for h?

[surfersss]

thanks! i learned c before, so i still used to it..
its work when type 100. but i got TLE now.
i changed it now to
long long *l = new long long [h];

do you have any other suggestions for TLE?
i think its because 3 for loop(?)

[jonnin]

where is your delete statement for the memory you got from new? This thing leaks memory like mad.

why do you allocate memory every loop instead of one time? Can you just re-use the memory?

sqrt(h) is a constant. why inside loop?

printing to console is slow. write to a file instead.

[jonnin]

I don't know what your time limit is, but I was able to generate all umpteen billion primes in the entire range in 30 seconds flat with this rather idiotic approach (its pure brute force but its brute force that the computer is GOOD at). If you pre-generate that you can just peel off what is in the range for each grouping from the input.

int main( int argc, char **argv)
    {	
	    int tm = clock();
		unsigned long long i,j,k;
		constexpr unsigned long long  big = 1000000000;	
		
		vector<bool> bt(big,true);
		for(i = 2; i < big; i++)
		{
		  if(bt[i])
             for(j = i*2; j < big; j+=i)
				 bt[j] = false;
			
		}		
		cout << (clock()-tm)/(double)CLOCKS_PER_SEC << endl;
   	        //for(j = 2; j < big; j++)
		// if(bt[j]) cout << j << endl;		
		return 0;
	}

if bt[x] is true, x is prime.
my best take at it using other methods took almost as long for just a million as this did for the whole range. you can probably tweak it even more somewhere. I don't see it, but it can't be optimal -- I didn't try to reduce the work so much as to do cheap work in bulk.

[jonnin]

Ah. I was able to unroll it one level and it almost cut in half from 30 sec to 18. It gets ugly in a hurry but you could probably do that 3 - 5 levels deep and have the full billion in just a few seconds without even threading anything.

one level looks like
i = 2;
for(j = i*2; j < big && bt[i]; j+=i)
bt[j] = false;

for(i = 3; i < big; i+=2)
{
for(j = i*3; j < big && bt[i]; j+=i*2)
bt[j] = false;
}

amusing, if nothing else.