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?

• DarthGizka: Your code can be speeded up by at least four to five orders of magnitude. Searching Code Review for topics like SPOJ PRIME1 should turn up hundreds of articles that give you all the necessary know-how... Keywords to watch out for are: 'segmented Sieve of Eratosthenes', 'wheeled striding' and 'L1 cache size'.
• DarthGizka: To put things into perspective: a decent solution in a language like C, C++, Pascal and so on should clock 0.00 s on SPOJ (there are untold thousands of submissions that do so, in these languages). It can get a tad more difficult in languages that are jitted or interpreted, though. My C# submission clocked 0.01 and I couldn't get it under 5 ms in order to achieve the eternal top rank as first 0.00. Hence I'm quite familiar with this particular problem. Beware, though: input/output performance can play a big role here (though C should be okay).
• Sjoerd Job Postmus: To me it is unclear as to what the purpose of the code is. What is the expected input (you covered it a bit), and what is the expected output? Could you write it up in a bit more detail?

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>

• DarthGizka: -1 because: sieving all primes up to 1,000,000,000 can be done in less than a second with fairly simple code, well within the generous time limit of the task (6 seconds or thereabouts). This means your opening statement is wrong. Moreover, coding challenge sites do not allow 'offline files' to be deposited so that a submission can load its results from such a file. Trying to hard-code the 50,847,543 primes up to 10^9 in the source requires in excess of 100 MByte even if you store only deltas; this will invariably exceed source code size limits for submissions. Your answer doesn't make sense.
• user3629249: @DarthGizka, My submission for this very question used exactly the method I proposed, where the precalculated list of primes was part of the source file (not a separate file) and it passed the judging. Running the same program, but where the values were calculated 'live' overran the available time allowed.