You are not logged in. Please login at www.codechef.com to post your questions!

×

PRIME1 solution

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;

}

asked 16 Jul '14, 15:35

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%


  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]
link

answered 16 Jul '14, 16:01

tec's gravatar image

5★tec
304118
accept rate: 21%

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.

(17 Jul '14, 15:22) dragonemperor3★

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.

(17 Jul '14, 16:09) tec5★

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.

link

answered 31 Mar '17, 19:08

swamicoder's gravatar image

4★swamicoder
2347
accept rate: 10%

@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;

}

link

answered 31 Mar '17, 19:16

shraeyas's gravatar image

3★shraeyas
1.3k2618
accept rate: 10%

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.

(31 Mar '17, 19:19) shraeyas3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×69

question asked: 16 Jul '14, 15:35

question was seen: 6,437 times

last updated: 31 Mar '17, 19:19