#### Тема: SPOJ: PRIME1 - Prime Generator

Вітаю! Намагаюсь вирішити цю задачу:
http://www.spoj.com/problems/PRIME1/
Ось код:

Прихований текст
/*

NOTE: CODE UPDATED 12-5-14

Name: Brian Butler
Professor: Gary Hartell
Date: September 22, 2011
Assignment: Sieve of Sundaram

Descripion:
This program uses the Sieve of Sundaram to find all of the prime numbers up to
and including the integer entered by the user.

Algorithm:(taken from Wikipedia.com)

Start with a list of the integers from 1 to n. From this list, remove all
numbers of the form i + j + 2ij where:

1)   i,j Elements of N, 1<= i<=j
2)   i + j + 2ij <= n

The remaining numbers are doubled and incremented by one, giving a list of the
odd prime numbers (i.e., all primes except the only even prime 2) below 2n + 2.

The sieve of Sundaram is equivalent to the sieve of Eratosthenes, except that
the initial list corresponds only to the odd integers; the work of "crossing out"
the multiples of 2 is done by the final double-and-increment step.
Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1,
Sundaram's method crosses out i + j(2i+1) for i <= j <= ( inputNumber / 2).

CALCULATIONS BELOW ARE TAKEN FROM:
http://en.wikipedia.org/wiki/Sieve_of_Sundaram
*/

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct my_bounds {
int lower;
int higher;
};

int main()
{
int cases = 0;                            // number of cases
const double highest_bound = 1000000000;  // max number from user input
double square_root = 0.0;                 // square root for the highest_bound
int upper_bound = 0;                      // upper bound for calculations

vector<int> primes;    // array of prime numbers
vector<int> temp;      // array for prime numbers that are inside given bounds

// Save number of cases into the memory and create set of bounds
cin >> cases;           // store the number of cases
my_bounds *bp[cases];   // array of pointers to use structures

for (int i = 0; i < cases; i++) {
bp[i] = new my_bounds;      // allocate memory for structures

cin >> bp[i]->lower;        // store user input using these structures
cin >> bp[i]->higher;
}

// CALCULATIONS BELOW ARE TAKEN FROM:
// http://en.wikipedia.org/wiki/Sieve_of_Sundaram

// precompute all primes smaller than sqrt(highest_bound)
square_root = sqrt(highest_bound);
square_root = ceil(square_root);
upper_bound = int(square_root);

// Fill the array with initial numbers (1, 2, ..., sqrt(highest_bound))
for (int i = 0; i < upper_bound; i++)
{
primes.push_back(i + 1);
}

int n = upper_bound / 2; // ? find the midpoint
int totalPrimes = 0;     // variable for the total number of prime numbers
//  that are found
int TheseArePrime = 0;   // variable used in the array that stores the prime
//  numbers found

for (int i = 1; i < n; i++)
{
for (int j = i;  j<= (n-i)/(2*i+1); j++)
{
primes[i + j + 2 * i * j] = 0;     /*From this list, remove all
numbers of the form i + j + 2ij    */
}
}

if (upper_bound >= 2)
{
primes[TheseArePrime++] = 2; /* this IF statement adds 2 to the output
* since 2 is a prime number    */
totalPrimes++;
}

for (int i = 1; i < n; i++)
{
if (primes[i] != 0)
{
primes[TheseArePrime++]=i*2+1;
/*The remaining numbers are
doubled and incremented by
one, giving a list of the
odd prime numbers (i.e., all
primes except the only even
prime 2) below 2n + 2.
*/

totalPrimes++;// the counter of the number of primes found
}
}

int lower = 0;          // current lower limit
int higher = 0;         // current higher limit
int found_primes = 0;   // how much primes are found
bool is_prime = true;   // flag that shows if the current number is prime

for (int i = 0; i < cases; i++) {
// initialize variables
lower = bp[i]->lower;
higher = bp[i]->higher;
found_primes = 0;
temp.clear();

if (higher <= primes.back()) {
/* Output numbers in given bounds from array with found primes */
for (int x = 0; primes[x] <= higher ; x++) {
if (primes[x] >= lower) {
cout << primes[x] << endl;
}
}
} else {
/* Create an array of primes inside given bounds */
for (int j = lower; j <= higher; j++)
{
is_prime = true;
for (int k = 0; k < totalPrimes; k++) {
if ( (j % primes[k]) == 0 ) { // Divide current number with
// all previous primes
is_prime = false;
break;
}
}
// Add found element to the array
if (is_prime) {
temp.push_back(j);
found_primes++;
}
}
// Output found numbers in the given range
for (int x = 0; x < found_primes; x++) {
cout << temp[x] << endl;
}
}

cout << endl;
}

for (int i = 0; i < cases; i++) {
delete bp[i];                       // free the memory
}

return 0;
}

Нібито працює як треба, але я отримую помилку: wrong answer.
Допоможіть, будь ласка!

#### Re: SPOJ: PRIME1 - Prime Generator

Випадково натрапив на рішення.
Програма працювала неправильно, коли нижня межа діапазону була менше ніж 31607, а верхня більше ніж 31607. Поправив програму і рішення підійшло на SPOJ:

/*

NOTE: CODE UPDATED 12-5-14

Name: Brian Butler
Professor: Gary Hartell
Date: September 22, 2011
Assignment: Sieve of Sundaram

Descripion:
This program uses the Sieve of Sundaram to find all of the prime numbers up to
and including the integer entered by the user.

Algorithm:(taken from Wikipedia.com)

Start with a list of the integers from 1 to n. From this list, remove all
numbers of the form i + j + 2ij where:

1)   i,j Elements of N, 1<= i<=j
2)   i + j + 2ij <= n

The remaining numbers are doubled and incremented by one, giving a list of the
odd prime numbers (i.e., all primes except the only even prime 2) below 2n + 2.

The sieve of Sundaram is equivalent to the sieve of Eratosthenes, except that
the initial list corresponds only to the odd integers; the work of "crossing out"
the multiples of 2 is done by the final double-and-increment step.
Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1,
Sundaram's method crosses out i + j(2i+1) for i <= j <= ( inputNumber / 2).

CALCULATIONS BELOW ARE TAKEN FROM:
http://en.wikipedia.org/wiki/Sieve_of_Sundaram
*/

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct my_bounds {
long lower;
long higher;
};

int main()
{
int cases = 0;                            // number of cases
const double highest_bound = 1000000000;  // max number from user input
double square_root = 0.0;                 // square root for the highest_bound
long upper_bound = 0;                     // upper bound for calculations

vector<int> primes;    // array of prime numbers
vector<int> temp;      // array for prime numbers that are inside given bounds

// Save number of cases into the memory and create set of bounds
cin >> cases;           // store the number of cases
my_bounds *bp[cases];   // array of pointers to use structures

for (int i = 0; i < cases; i++)
{
bp[i] = new my_bounds;      // allocate memory for structures

cin >> bp[i]->lower;        // store user input using these structures
cin >> bp[i]->higher;
}

// CALCULATIONS BELOW ARE TAKEN FROM:
// http://en.wikipedia.org/wiki/Sieve_of_Sundaram

// precompute all primes smaller than sqrt(highest_bound)
square_root = sqrt(highest_bound);
square_root = ceil(square_root);
upper_bound = long(square_root);

// Fill the array with initial numbers (1, 2, ..., sqrt(highest_bound))
for (long i = 0; i < upper_bound; i++)
{
primes.push_back(i + 1);
}

long n = upper_bound / 2; // ? find the midpoint
long totalPrimes = 0;     // variable for the total number of prime numbers
//  that are found
long TheseArePrime = 0;   // variable used in the array that stores the prime
//  numbers found

for (long i = 1; i < n; i++)
{
for (long j = i;  j<= (n-i)/(2*i+1); j++)
{
primes[i + j + 2 * i * j] = 0;     /*From this list, remove all
numbers of the form i + j + 2ij    */
}
}

if (upper_bound >= 2)
{
primes[TheseArePrime++] = 2; /* this IF statement adds 2 to the output
* since 2 is a prime number    */
totalPrimes++;
}

for (long i = 1; i < n; i++)
{
if (primes[i] != 0)
{
primes[TheseArePrime++]=i*2+1;
/*The remaining numbers are
doubled and incremented by
one, giving a list of the
odd prime numbers (i.e., all
primes except the only even
prime 2) below 2n + 2.
*/

totalPrimes++;// the counter of the number of primes found
}
}

long lower = 0;          // current lower limit
long higher = 0;         // current higher limit
long found_primes = 0;   // how much primes are found
bool is_prime = true;   // flag that shows if the current number is prime

for (int i = 0; i < cases; i++)
{
// initialize variables
lower = bp[i]->lower;
higher = bp[i]->higher;
found_primes = 0;
temp.clear();

/* Create an array of primes inside given bounds */
for (long j = lower; j <= higher; j++)
{
if (j == 1) {
continue;
}
is_prime = true;
for (int k = 0; primes[k] < j && k < totalPrimes; k++)
{
if ( (j % primes[k]) == 0 )
{ // Divide current number on
// all previous primes
is_prime = false;
break;
}
}
// Add found element to the array
if (is_prime)
{
temp.push_back(j);
found_primes++;
}
}
// Output found numbers in the given range
for (long x = 0; x < found_primes; x++)
{
cout << temp[x] << endl;
}

cout << endl;
}

for (int i = 0; i < cases; i++)
{
delete bp[i];                       // free the memory
}

return 0;
}