PRIME1 solution

general
1

Hello guys, I am stuck in a medium level problem PRIME1. I used sieve to generate primes upto 32000 (My first sieve implementation, so if it is wrong, please point out.) and used those primes to generate all others, but I am getting TLE. I have looked previous posts and answers in the editorial but was not able to solve it. Please help.

Here is the id of the solution : 4335757

I am also posting it here :

#include<stdio.h>

#define MAX_PRIME 32000

int primes[MAX_PRIME],req_prime[MAX_PRIME];

int total_prime=0;

/Initialise the array to 1/

void set_to_one()

{

for(int i=0;i<MAX_PRIME;i++)

	primes[i]=1;

}

/Finds primes upto 32000 and puts them in another array req_prime/

void preprocess()

{

primes[0]=primes[1]=0;

for(int i=2;i<MAX_PRIME;i++)

{

	if(primes[i])

	{

		req_prime[total_prime++]=i;

		for(int j=i+i;j<MAX_PRIME;j+=i)

		{

			primes[j]=0;

		}

	}

}

}

/Just to check if all primes are identified or not. They are for debugging only./

void print_all_primes()

{

for(int i=0;i<MAX_PRIME;i++)

	printf("%d\t",primes[i]);

}

/To check if the number is a prime or not/

void check_prime(int n)

{

int count=0;

for(int i=0;i<total_prime;i++)

{

	if(n%req_prime[i]==0 && n!=req_prime[i])

			count++;

	

	if(req_prime[i]>=n)

		break;

}

if(count==0 && n!=1)

	printf("%d\n",n);

}

/* Checks all numbers in the array */

void solve_problem(int arr[],int size)

{

for(int i=0;i<size;i++)

{

	check_prime(arr[i]);

}

}

int main()

{

int test,a,b;

scanf("%d",&test);

set_to_one();

preprocess();

//print_all_primes();

while(test--)

{

	scanf("%d%d",&a,&b);

	int arr[b-a+1];

	for(int i=a;i<=b;i++)

		arr[i-a]=i;

	solve_problem(arr,b-a+1);

}

return 0;

}

2
  1. your prime sieve is right, but start from j=i*i instead of j=i+i could speed up a lot.
  2. your check_prime contains a loop up to 32000, and it could be called 100000 times at maximum, so the total comparison times can be up to 3.2*10^9, which definitely TLE. you should use another sieve, using req_prime[MAX_PRIME] to sieve out the primes in [m…n]
3

I took your advice and implemented this :

http://www.codechef.com/viewsolution/4338469

But I am still getting TLE. For my test cases, previous implementation took about 18 seconds, but now it takes less than 2 seconds. But, I am still getting TLE.

Please reply.

4

Modulo operations (arr[n]%req_prime[i]) in check_prime() cost too much time. (you can count the operations taking random range with length 10^5). Your sieve should be similar to the one in preprocess(). for each prime, find the first multiple in range, and filter out all multiples. After all filters, only primes remain, then you can look through the array and collect primes.

5

Can, someone please explain, how to deal with such large inputs. Also I have tried to look at few solutions. I found this one to be easiest one, but not been able to understand that why is he getting right answer.

6

@swamicoder this one should be easy to understand.

#include <stdio.h>
#include<math.h>

int P_G(long n)
{
if(n==1)
return 0;

if(n==2)
return 1;

if(n%2==0)
return 0;

for(long i=3;i<=sqrt(n);i+=2)
{
	if(n%i==0)
	return 0;
}
return 1;

}

int main()
{
int t;
scanf("%d",&t);

while(t--)
{
	long n,m;
	scanf("%ld %ld",&n,&m);
	
	for(long i=n;i<=m;i++)
	{
		if(P_G(i)==1)
		printf("%ld\n",i);
	}
}
return 0;

}

7

What I have done is simply check if a number is zero, one or even (other than 2), in those cases we can immediately tell that number is not prime.

For other numbers, just run a loop from 3 to sqrt of that number and check if that number is divisible by those numbers (the loop variables). If it is so, then the number is not prime else it is prime.