SPOJ - Prime1

[rozick1]

Hi

I'm trying SPOJ Prime1 (http://www.spoj.com/problems/PRIME1/) where I need to write a segmented sieve of eratosthenes. The below seems to work except for primes which are smaller than the root of n

  #include <iostream>
#include <vector>
#include <math.h>



void generate_primes(long long int m, long long int n)
{

	std::vector <bool> sieve  (n+1,true);
	std::vector <long long int> primes;


	sieve[0] = false;
	sieve[1] = false;

	//sieve

	for (long long int i= 2; i<sqrt(n+1); i++)
	{
		if (sieve[i] == false)
			continue;

		for (long long int j=i+i;j<sqrt(n+1); j+=i)
				sieve [j] = false;
	
	}
	
	for (long long int i=0; i < sqrt(n+1);i++)
		if (sieve[i] == true)
			primes.push_back(i);
			

	//delete sieve;

	std::vector<bool>().swap( sieve);
	

	//start segment sieve

	std::vector <bool> final_sieve (n+1,true);

	for (int i=0; i < primes.size();i++)
	{
		long long int first_multiple = m/primes[i] * primes[i];

		for (int j=first_multiple ; j<n+1; j += primes [i])
		{

			final_sieve[j] = false;
			
		}
	}

	//print
	for (int i=m; i < n+1; i++)
		if (final_sieve[i]==true)
			std::cout << i<<std::endl;

}


int main()
{
	

generate_primes(1,300);

}

Thanks!

[ne555]

long long int first_multiple = m/primes[i] * primes[i];
for (int j=first_multiple ; j<n+1; j += primes [i])

first_multiple may be prime.

std::vector <bool> final_sieve (n+1,true);
considering the limits of the problem, that's a bad idea.