Please help me in prime1 using c

[learntocode]

I am trying to solve the PRIME1 problem of SPOJ using Sieve of Eratosthenes. The code works fine for lower integers but shows the following error for long ints. I am still getting an error for large numbers. Example - code runs fine for m = 100000000 and n = 110000000 but shows the following error for m = 999899999 and n = 999999999. The error is - "Unhandled exception at 0x778a15ee in spoj1.exe: 0xC0000005: Access violation writing location 0x00000000." Similar error is shown by SPOJ - "SIGSEGV" error. Please help. Also, I am new to coding so please bear with any egregious mistakes.

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int m, n, test, i, k;
    long int *arr, p;
    scanf("%d", &test);

while (test--)
{
    scanf("%d%d", &m, &n);

    arr = (long int *)calloc(n - 1, sizeof(long int));

    if (m == 1)
    {
        m = 2;
    }
    arr[0] = 2;

    for (i = 1; i < n - 1; i++)
    {
        arr[i] = arr[i - 1] + 1;
        // printf("%d\n",arr[i]);
    }

    for (i = 0; i < n - 1; i++)
    {
        if (arr[i] != 0)
        {
            for(k = arr[i]-2; k<n-1;)
    {
        k = k + arr[i];
        if(k < n-1)
        {
            arr[k] = 0;


        }
        }
    }

    for (i = 0; i < n - 1; i++)
    {
        if (arr[i] != 0 && arr[i] >= m)
        {
            printf("%d\n", arr[i]);
        }
    }

    printf("\n");
}

free(arr);
return 0;
}

[leppyr64]

arr = (long int *)calloc(n - 1, sizeof(long int));

You cannot declare an array this large. It uses far too much memory causing the SIGSEGV.

Think about it this way. A long int is a 32 bit signed integer. 32 bits is 4 bytes. 4*999999999 bytes in gigbaytes is 4. 4 GB! Most OS cap the available RAM at 2GB.

[learntocode]

oh...yes I did not know if such problem can exist. Thanks you
But then what should i do? If i want to solve this using sieve method, then I should start from number '2' irrespective of what my lower limit 'm' is...right?

[leppyr64]

What is the definition of a prime number? Simplify this term. A number only divisible by 1 and itself is not a simplified definition.

Knowing the definition of a prime use the constraints that are small to your advantage.

[learntocode]

ok...so I have now simplified everything...rewritten my code and it gives instant result of the test cases you gave me. I even tried it on ideone.com and it ran well within 5sec window. Even the, SPOJ shows the segmentation fault error. I just dont know whats wrong with it My code is -

#include<stdio.h>
#include<math.h>
int main()
{
	long int a[10001],m,n,l;                         //here i have tried both with int and long int but still SPOJ shows the same result
	int test,i,k,d;
	double p, o;
    scanf("%d",&test);

while(test--)
{
	scanf("%d%d",&m,&n);

	if(m == 1)
	{
		m = 2;
	
	}
	
	a[0] = m;

	for(i=1;i<10001;i++)
	{
		if( i <= n-m)
		{
			a[i] = a[i-1] + 1;
	
		}
	
		else 
		{
			a[i] = 0;
		
		}

	}





o = n;
	
	p = sqrt(o);

	l = p;

	for(i = 2; i<=l; i++)
	{
		for(k = (m/i) - 1 ;k< (n/i)+1 ; k++)
		{
			if(i*k >= m && k!=1)
		{
			d = (i*k) - m;
			a[d] = 0;
		
		}
		
		}
		
	
	
	}
	
		for(i = 0; i<10001; i++)
	{
		if(a[i] != 0)
		{
		printf("%d\n",a[i]);
		}
	
	}
	
	



  if( test!=0 )
  {
	  printf("\n");
  
  }


}



return 0;
}

[leppyr64]

10000?

[learntocode]

Yes that was the mistake...I finally got it accepted by using dynamic memory allocation...Thanks for all the help

[Manan_sof]

Sorry to paste code here.
Can anybody look why the code gives time exceeded.
Link to code :- ideone.com/2VIVdB#stdin

Code

include

include

include

bool isPrime(int);
using namespace std;
int main()
{
int num_of_input, *from= NULL, *to=NULL;
std::cin >> num_of_input;
if (!num_of_input)
return 0;
from = (int*)malloc(sizeof(int));
to = (int*)malloc(sizeof(int));
if( !from || !to )
return 0;
int i=0, j=0;
for(i=0; i{
std::cin >> from[i];
std::cin >> to[i];
}

for(i=0;i< num_of_input; i++)
{
for(j=from[i]; j<=to[i]; j++)
{
if(j==1 || j==0)
continue;
else if(isPrime(j))
std::cout << j << " ";
}
std::cout << endl;
}

free(from);
free(to);
return 0;
}

bool isPrime(int n)
{
for (int i=2; i<=int(sqrt(n)); i++)
{
if (n%i == 0)
return 0;
}
return 1;
}

[leppyr64]

Please use code tags when posting code.

Your code gets TLE because your algorithm is too slow. You need to reduce the amount of work that you do in loops. Storing information in memory might be useful.

[Manan_sof]

Hi, I think I am using the best possible primality test so far (For normal people, not number theory ). I am not getting why you are saying I have to reduce the processing inside the loop. Can you show me the line which cause the problem.
Or you are saying to hard code everything instead of using dynamic memory allocation.

[leppyr64]

The function isPrime is the portion that is too slow.

Your definition of a prime number is:
"A number that is not divisible by a number less tha n it's root"

This means that you will need to look at sqrt(n) numbers for any prime. You can reduce this by doing some precalculation.

You cannot hard code this problem.

As a general tip: In general cin and cout are really slow. Use scanf and printf.

[lavantien]

You don't need any hardcore array or any advanced method, such as sieve or prime generate. Anything you need is a "basic prime checking method" and optimize it a little bit (I learn this "basic prime checking method" on Wiki, so you may be look at this keyword for Google search: "Primality test").

Here is my code which is "accepted", using 2.0M of memory and about 0.6s runtime.

Removed AC code