1 / 2
Jan 2020

I have used Segmented Sieve Algorithm to solve this problem. But at the end of struggling for days :crazy_face: I’m getting SIGPFE error.

Found that this error is either due to :

  1. Division by Zero or
  2. Integer Overflow

I’m not able to figure out where my code is going wrong :thinking:, since it is running on my PC well and good. The code is below :


#include <bits/stdc++.h>
using namespace std;
#define ull long long unsigned int
#define ll long long int
#define ld long double
#define SPEED ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const unsigned int M = 1000000007;

vector<ull> prim;

void simpleSieve(ull k, vector<ull> &primes)
{
	bool mark[k + 1];
	memset(mark, true, sizeof(mark));

	for (size_t p = 2; p * p <= k; ++p)
	{
		if (mark[p])
		{
			for (size_t i = p * 2; i <= k; i += p)
			{
				mark[i] = false;
			}
		}
	}

	for (size_t i = 2; i < k + 1; i++)
	{
		if (mark[i])
		{
			primes.push_back(i);
		}
	}
}

void solve()
{
	ull L, U;
	cin >> L >> U;

	ull k = (ull)sqrt(U);

	bool mark[U - L + 1];
	memset(mark, true, sizeof(mark));

	ull loLim = 0;

	for (size_t i = 0; prim[i] <= k; ++i)
	{
		loLim = floor(L / prim[i]) * prim[i];
		if (loLim < L)
			loLim += prim[i];
		if (loLim == prim[i])
			loLim += prim[i];

		for (size_t j = loLim; j <= U; j += prim[i])
		{
			mark[j - L] = false;
		}
	}

	for (size_t i = 0; i < U - L + 1; i++)
	{
		if (mark[i])
			cout << (ull)i + L << "\n";
	}
}

int main()
{
	SPEED;
	int t = 0;
	cin >> t;

	simpleSieve((ull)4632, prim);


	for (size_t i = 0; i < t; i++)
	{
		solve();
	}
	return 0;
}

Any help is appreciated :hugs:

  • created

    Jan '20
  • last reply

    Jan '20
  • 1

    reply

  • 847

    views

  • 2

    users

  • 1

    link

Have you tried it on IDEONE? The environment there will likely be closer to SPOJ’s than your own PC, since both are provided by Sphere.