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

×

Sigsegv error even after using segmented sieve of Eratosthenes

I am getting a sigsegv error in SPOJ Prime1 problem even after using segmented sieve of eratosthenes http://www.spoj.com/problems/PRIME1/

#include<iostream>
#include<cmath>
using namespace std;

int main()
  {
   int prime[100000];
   int myprime[100000];
   long long int m,n,i,j,q,s,r,w,p;
   int t,range;
   cin>>t;
   while(t--)
     {
        r=0;

       cin>>m>>n;
       range=floor(sqrt(((double)n)));
       prime[0]=0;
       prime[1]=0;
       for(i=2;i<=n;i++)
        prime[i]=1;

       for(i=2;i<=range;i++)
       {

       if(prime[i]==1)
          {
          for(j=2;i*j<=n;j++)
              {

                prime[i*j]=0;
              }

          }
       }

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

          if(prime[i]==1)
             {
             myprime[r]=i;
             r++;
             }
          }

        for(i=0;i<r;i++)
        {

           w=m/myprime[i];         
           w=w*myprime[i];             
           p=myprime[i];

           for(s=w;s<=n;s=s+p)   
              {

              if(prime[s]==1)
                 {
                 for(q=2;s*q<=n;q++)    //possible bug
                    {
                    prime[s*q]=0;
                    }
                 }
              }
         }

         for(i=m;i<=n;i++)
         {
           if(prime[i]==1)
           {
               cout<<i<<"\n";

           }
         }
       cout<<"\n";


      }




       return 0;

        }

asked 24 Sep '15, 12:58

artist's gravatar image

1★artist
23214
accept rate: 0%

edited 24 Sep '15, 13:07


You have written:

for(int i = 2 ; i <= n ; i++)
    prime[i] = 0;

What if n is greater than $10^{5}$? The size of array prime is only $10^{5}$ so you are trying to index an element which does not exist, thus segmentation fault.

Edit 1: My solution

We know that a number $N$ is a prime if it is not divisible by any number in the range $[2, \sqrt{N}]$. Extending this statement, we can say that any number between $[2, 10^{9}]$ will be a prime number if it is not divisible by any number in the range $[2, \sqrt{10^{9}}]$ which is equal to $[2, 31624]$ (approximately). We can find all the prime numbers in this range easily using Sieve of Eratosthenes. Do this and store all prime numbers in this range in an array. Now, you can use this array to find all prime numbers in any range $[m, n]$.

Edit 2:

Let's assume a test case: $m = 2, n = 24$

First, we will make an auxiliary array to represent all numbers in the range $[m, n]$ (note that in the question it is given that $n-m<=10^{5}$, so we can do this without fear of segmentation fault). In this array, we will strike out the multiples of all prime numbers ($pk$ where $p$ is a prime number less than or equal to $\left \lfloor \sqrt{n} \right \rfloor$ and $k > 1$) and the remaining numbers will be prime in that range. ex:

$2 \ \ 3 \ \ 4 \ \ 5 \ \ 6 \ \ 7 \ \ 8 \ \ 9 \ \ 10 \ \ 11 \ \ 12 \ \ 13 \ \ 14 \ \ 15 \ \ 16 \ \ 17 \ \ 18 \ \ 19 \ \ 20 \ \ 21 \ \ 22 \ \ 23 \ \ 24 $

Removing all numbers of the form $2k$ where $k > 1$, this will become:

$2 \ \ 3 \ \ 5 \ \ 7 \ \ 9 \ \ 11 \ \ 13 \ \ 15 \ \ 17 \ \ 19 \ \ 21 \ \ 23$

Removing all numbers of the form $3k$, where $k > 1$, this will become:

$2 \ \ 3 \ \ 5 \ \ 7 \ \ 11 \ \ 13 \ \ 17 \ \ 19 \ \ 23$

Here, we check that $\left \lfloor \sqrt{24} \right \rfloor = 4$ and we have removed factors of all prime numbers less than or equal to $4$. The remaining numbers are all prime numbers. In this way we can solve it for any given $[m, n]$.

You can optimise the way in which you struck out the numbers. One naive way is to iterate through the array for every prime number ($<=\left \lfloor \sqrt{n} \right \rfloor$) and strike out the numbers which satisfy the condition. An optimised way will be to do some computation to calculate the first number that needs to be struck and the advance the array with i += p instead of i++. I was able to achieve a minimum time of 0.09 secs.

link

answered 24 Sep '15, 13:32

shubhambhattar's gravatar image

3★shubhambhattar
2889
accept rate: 23%

edited 26 Sep '15, 14:39

could you suggest an alternative as I can't increase the array size as it is maximum possible

(24 Sep '15, 13:52) artist1★

What do you mean by "maximum possible"? You should be able to allocate much larger arrays than 10^5 (either globally or dynamically). If you mean that you can't go up to 10^9 you're right.

(25 Sep '15, 11:07) ceilks7★

@ceilks -I meant that I can't go upto 10^9 and @shubhambhattar -I coded it but it is not working https://ideone.com/ig3vus

(25 Sep '15, 17:21) artist1★

@artist Can you elaborate what problem you are facing (WA, TLE, SIGSEGV) or if you know a particular case where your code is giving wrong answer then give it. Also, I noticed one thing in your code, you are calculating the prime numbers in each test case, you don't need to do that. That is redundant work and will unnecessarily increase running time of your program. You should do it only once, probably before the loop "while(t--)" and use it in each test case. Edit: Also put more comments as it will be easier to understand.

(25 Sep '15, 17:32) shubhambhattar3★

I am getting a sigsegv error ,also my logic is incorrect

(25 Sep '15, 23:48) artist1★

Line no. 30 is where your code is giving segmentation fault. Suppose i = 2, then the maximum value that j will attain in your loop will be n/2 and i*j can go upto n. Size of array prime is $10^5$ and for large values of n (like $10^9$), your code will try to index an element which does not exist. That will give Segmentation Fault. Check this out: https://ideone.com/IwMUtS . variable j cannot go greater than 12774.

(26 Sep '15, 13:59) shubhambhattar3★

I changed my code actually the problem is in the code-snippet which marls offsets in the range and I am unable to figure out the logic to do it https://ideone.com/Ryhi9Q

(26 Sep '15, 18:26) artist1★

@artist Your implementation of Sieve is wrong. Read how to implement Sieve here under topic algorithm and variants : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes . I have explained the complete logic of the problem in my answer. If you can implement it successfully, you will get AC.

(27 Sep '15, 01:13) shubhambhattar3★
showing 5 of 8 show all
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:

×1,917
×1,137
×303
×199

question asked: 24 Sep '15, 12:58

question was seen: 1,132 times

last updated: 27 Sep '15, 01:14