Problem in Sieve of Eratosthenes

#1

I have written a code which takes in n(no of prime numbers to find) and k(upto which they could be found) …
but it is showing error for larger values and giving error while running …
this is my code…

#2

Please note that in line 9 and line 12, there can be overflow for larger values of i (due to i*i).

#3

yes i did that but when i am running in my compiler it is hanging after giving the output for a sec then returnig some garbage insted of 0

#4

Okay, that might be due to difficulty in dynamically allocating large sized array (avoid using dynamic allocation (using new()) as far as possible).

I changed your code to one which uses vector and it works fine.

#include<bits/stdc++.h>
using namespace std;

vector<int> prime_array(int n,int k)
{
    int arr[k]={0};
    bool prime[k+1];
    memset(prime,true,sizeof(prime));
    for(long long i=2;i*i<=k;i++)
    {
       if(prime[i]){
        for(long long j=i*i;j<=k;j+=i)
        {
            prime[j]=false;
        }
       }
    }
    int c=0;
    for(int i=2;i<=k;i++)
    {
        if(prime[i])
        {
            arr[c++]=i;
        }
    }

    vector<int> brr(n);
    for(int i=0;i<n;i++)
    {
        brr[i]=arr[i];
    }
    return brr;
}
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> arr = prime_array(n,k);
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
	return 0;
}
#5

Thanks man !! Could you please tell why new got an error…and why vector worked out well?

#6

In short
Never use new in competitive programming, there are several hidden factors associated with it. (you can always get away with a vector or similar in C++)

Long Answer
General purpose memory allocators have to handle the program requesting new memory and freeing old memory at arbitrary points during execution. There are many ways to do this but they all have some memory overhead. One common way is for each chunk of memory to store a pointer to the next available chunk. If you look up “program your own malloc” or something similar there will probably be some resources.

For competitive programming, usually you just want to allocate memory and you never have to free it. I would almost never use the default new in CP.

#7

so basically it means when i was using new…it randomly picked up memeory from heap(probably starting from the end) and connected the chunks using a pointer…now after several allocations it will come to a point in heap which is already allocated…thus it sohws error??? Is it so?

#8

No basically it tries to allocate continuous memory in the heap (as it is an array, so continuous). But it will have trouble as such large amount of continuous memory is not always available (leading to various allocations and deallocations), also there are some memory overheads associated with the memory allocation (which further add to the problem).

1 Like