1 / 2
Jun 2009

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;
            }
        }
    }
}
  • created

    Jun '09
  • last reply

    Jun '09
  • 1

    reply

  • 175

    views

  • 2

    users

The first thing you should look for with SIGSEGV is array indices out of bounds.. and I found that straight away in your main method smile Check what those indices can be carefully and you'll easily find your mistake.

I'm not quite sure what you meant by the remainder of your post, but if you're saying a Wrong Answer should always give you the test case you failed on, definitely not - that would make debugging a problem far too easy. No contest will ever do that; you should be able to debug the program yourself.

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 14 7d

Want to read more? Browse other topics in C and C++ or view latest topics.