Prime numbers in given range

Question

SPOJ problem PRIME1 (also found on other sites in identical form):

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

My Answer:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int iter = 0;
    scanf("%d",&iter);
    while(iter--) {
        long num1, num2;
        scanf("%ld%ld",&num1,&num2);

        long prime[60000];
        prime[0] = 2;
        long prime_count = 1;
        long result[60000];
        long result_count = 0;

        if(num1 <= 2){
            result[0] = 2;
            result_count++;
            printf("2\n");
        }

        for(long i = 3; i <= num2; i++) {
            int isPrime = 1;

            for(long j = 0; j < prime_count; j++) {
                if(i % prime[j] == 0) {
                    isPrime = 0;
                    break;
                }    
            }
            if(isPrime) {
                prime[prime_count] = i;
                prime_count++;
                if(i >= num1){
                    result[result_count] = i;
                    result_count++;
                    printf("%ld\n",i);
                }
           }
        }
        printf("\n");
    }

    return 0;
}

Is there any way to improve my code?

Answer 1

well, calculating all the primes from 2 through 1000000000 will take too long.

Suggest pre-calculating (offline) all those primes and output them into a .txt file.

Then edit that file into a C data table of size_t values.

then in your program, paste that text file into the file scope of your program. I.E. outside of any function.

remove those massive 60000 arrays from your program. All you really need is a counter to count the primes in the range n...m

In the offline program, use the Sieve of Eratosthenes algorithm (use google to find the algorithm)

using scanf() and 'printf()` burns LOTs of precious time.

suggest using the following functions for fast read/write of a Number. Use repeated calls to putc_unlocked() to output a string. Note: Be sure to output a final '\n' so the output ends in a blank line.

#include <stdio.h>

void fastRead( size_t *a );
void fastWrite( size_t a );

inline void fastRead(size_t *a)
{
    int c=0;
    // note: 32 is space character
    while (c<33) c=getchar_unlocked();

    // initialize result value
    *a=0;

    // punctuation parens, etc are show stoppers
    while (c>47 && c<58)
    {
        *a = (*a)*10 + (size_t)(c-48);
        c=getchar_unlocked();
    }
    //printf( "%s, value: %lu\n", __func__, *a );
} // end function: fastRead


inline void fastWrite(size_t a)
{
    char snum[20];
    //printf( "%s, %lu\n", __func__, a );

    int i=0;
    do
    {
        // 48 is numeric character 0
        snum[i++] = (char)((a%10)+(size_t)48);
        a=a/10;
    }while(a>0);

    i=i-1; // correction for overincrement from prior 'while' loop

    while(i>=0)
    {
        putchar_unlocked(snum[i--]);
    }
    putchar_unlocked('\n');
} // end function: fastWrite

Then your program only needs to do the following:

in English:

input numbertestcases
while decrement numbertestcases > 0 
    input 'n'
    input 'm'

    set primescount = 0

    for ( size_t x=0; 
          m <= primestable[x] 
          &&   
          x < sizeof( primestable )/ sizeof( *primestable );
          increment x)
        if primestable[x] >= n 
             increment primescount
        endif
    end for

    output primescount
    output '\n'
end for

output '\n'

then:

1. the code will be VERY fast
2. no need for #include <string.h>
3. no need for #include <math.h>
4. probably no need for #include <stdlib.h>