checked all types & initialization,
tested all side cases & code 2 case generators: no SIGSEGV.
can anyone help out me here?
code will be below.
Why won't to send input case in case of error for test case (not compilation or so on)?
If you have a valid program, you can generate a lot of input/output cases, so "look over" won't be a problem here.
#include <iostream>
#include <math.h>
using namespace std;
typedef unsigned long ulong;
const ulong bmax = 31622;
ulong sqrt_bmax = (ulong)sqrt((long double)bmax);
bool is_prime_begin[bmax];
// calculate first bmax prime numbers (their quadrates will be used for atkin algo for [n,m<=1 000 000 000])
void atkin();
const ulong limit = 100001;
bool is_prime[limit];
// calculate prime numbers in between [a,b], b-a <= 100000
void atkin(ulong a, ulong b);
int main() {
atkin();
ulong t;
cin >> t;
for(ulong i=0; i<t; i++) {
ulong m,n;
cin >> m >> n;
if(m > bmax) {
atkin(m,n);
for(ulong j=0; j<n-m; j++)
if( is_prime[j] )
cout << m+j << endl;
cout << endl;
} else {
for(ulong j=m; j<=n; j++)
if( is_prime_begin[j] )
cout << j << endl;
cout << endl;
}
}
return 0;
}
// calculate prime numbers in between [a,b], b-a <= 100000
void atkin(ulong a, ulong b) {
// initializing sieve
for(ulong i = 0; i <= b-a; i++)
is_prime[i] = false;
// supposing prime are integer with odd representation in given quadratic forms
// x2 и y2 - quadrates of i & j (optimization).
ulong x2 = 0;
ulong sqrt_b = (ulong)sqrtl((long double)b);
for(ulong i = 1; i <= 1+sqrt_b; i++) {
x2 += 2*i - 1;
// 4*x2 + y2 >= a => y2 >= a - 4*x2
// 4*x2 + y2 <= b => y2 <= b - 4*x2
ulong j = (a > 4*x2) ? 1+(ulong)sqrtl((long double)(a-4*x2)) : 1;
ulong jmax = (b > 4*x2) ? (ulong)sqrtl((long double)(b-4*x2)) : 0;
ulong y2 = j*j;
for( ; j <= jmax; j++) {
ulong n = 4 * x2 + y2;
if(n % 12 == 1 || n % 12 == 5)
is_prime[n-a] = !is_prime[n-a];
y2 += 2*j + 1;
}
// 3*x2 + y2 >= a => y2 >= a - 3*x2
// 3*x2 + y2 <= b => y2 <= b - 3*x2
j = (a > 3*x2) ? 1+(ulong)sqrtl((long double)(a-3*x2)) : 1;
jmax = (b > 3*x2) ? (ulong)sqrtl((long double)(b-3*x2)) : 0;
y2 = j*j;
for( ; j <= jmax; j++) {
ulong n = 3 * x2 + y2;
if(n % 12 == 7)
is_prime[n-a] = !is_prime[n-a];
y2 += 2*j + 1;
}
// 3*x2 - y2 >= a => y2 <= 3*x2 - a
// 3*x2 - y2 <= b => y2 >= 3*x2 - b
j = (3*x2 > b) ? 1+(ulong)sqrtl((long double)(3*x2-b)) : 1;
jmax = (3*x2 > a) ? (ulong)sqrtl((long double)(3*x2-a)) : 0;
y2 = j*j;
for( ; j <= jmax && i > j; j++) {
ulong n = 3 * x2 - y2;
if(n % 12 == 11)
is_prime[n-a] = !is_prime[n-a];
y2 += 2*j + 1;
}
}
// sieves quadrates of prime number in interval [5, min{sqrt(b), sqrt(bmax)}]
// main stage can't do it
for(ulong i = 5; i <= ((sqrt_bmax < sqrt_b) ? sqrt_bmax : sqrt_b); i++) {
if(is_prime_begin[i]) {
ulong i2 = i*i;
if(a < i2)
continue;
ulong n = ulong(a/(i2));
n = (1+n)*i2;
for(ulong j = n; j <= b; j += n) {
is_prime[j-a] = false;
}
}
}
}
void atkin() {
// initializing sieve
for(ulong i = 0; i <= bmax; i++) is_prime_begin[i] = false;
is_prime_begin[2] = true;
is_prime_begin[3] = true;
// supposing prime are integer with odd representation in given quadratic forms
// x2 и y2 - quadrates of i & j (optimization).
ulong x2 = 0;
for (ulong i = 1; i <= sqrt_bmax; i++) {
x2 += 2 * i - 1;
ulong y2 = 0;
for (ulong j = 1; j <= sqrt_bmax; j++) {
y2 += 2 * j - 1;
ulong n = 4 * x2 + y2;
if ((n <= bmax) && (n % 12 == 1 || n % 12 == 5))
is_prime_begin[n] = !is_prime_begin[n];
// n = 3 * x2 + y2;
n -= x2; // optimization
if ((n <= bmax) && (n % 12 == 7))
is_prime_begin[n] = !is_prime_begin[n];
// n = 3 * x2 - y2;
n -= 2 * y2; // optimization
if ((i > j) && (n <= bmax) && (n % 12 == 11))
is_prime_begin[n] = !is_prime_begin[n];
}
}
// sieves quadrates of prime number in interval [5, sqrt(bmax)]
// main stage can't do it
for (ulong i = 5; i <= sqrt_bmax; i++) {
if (is_prime_begin[i]) {
ulong n = i * i;
for (ulong j = n; j <= bmax; j += n) {
is_prime_begin[j] = false;
}
}
}
}
