# I have a problem understanding a solution for number theory problem from SPOJ [closed]

Problem statement can be found here or down below.

The solution which I'm trying to understand can be found here or down below.

Problem Statement.

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

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.

Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Solution

Concept:
The idea behind solution here is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion.
That square root happens to be around 32000.
Using this array, do a bounded Sieve of Eratosthenes only in the range requested.

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

int main() {
int primes[4000];
int numprimes = 0;

primes[numprimes++] = 2;
for (int i = 3; i <= 32000; i+=2) {
bool isprime = true;
int cap = sqrt(i)+1;
for (int j = 0; j < numprimes; j++) {
if (primes[j] >= cap) break;
if (i % primes[j] == 0) {
isprime = false;
break;
}
}
if (isprime) primes[numprimes++] = i;
}

int T,N,M;
scanf("%d",&T);

for (int t = 0; t < T; t++) {
if (t) printf("\n");
scanf("%d %d",&M,&N);
if (M < 2) M = 2;

int cap = sqrt(N) + 1;

bool isprime[100001];
memset(isprime,true,sizeof(isprime));

for (int i = 0; i < numprimes; i++) {
int p = primes[i];

if(p >= cap) break;

int start;

if (p >= M) start = p*2;
else start = M + ((p - M % p) % p);

for (int j = start; j <= N; j += p) {
isprime[j - M] = false;
}
}

int start = (M % 2)?M:M+1;

if (M == 2) {
printf("2\n");
}
for (int i = start; i <= N; i+=2) {
if (isprime[i-M]) printf("%d\n",i);
}
}
return 0;
}


I know how Sieve of Eratosthenes works and I also ran this program using pen and paper.
It works fine but I 'm not able to understand why it works and how do I prove that this program and the algorithm used in it are right?
I spent hours but could not prove.

Any help would be appreciated.

• This is basically just the sieve of Eratosthenes. I suggest spending a few days thinking about it. – Yuval Filmus Sep 30 '16 at 5:51

A number is prime if it has no non-trivial factors. In order to check whether a number $n$ is prime, it suffices to check that it has no factors in the range $2,\ldots,\sqrt{n}$. In order to find all primes in $[a,b]$, we go over all primes in $2,\ldots,\sqrt{b}$ (using a list prepared ahead of time), and for each such prime $p$, we mark off all multiples of $p$ in $[a,b]$. After going over all such primes, the unmarked numbers in $[a,b]$ are prime.
How do we mark off all multiples of $p$ in $[a,b]$? We mark off the first multiple $p \lceil a/p \rceil$ (computed in a funny way in the code), if it happens to fall inside the interval (but not if this multiple happens to be $p$ itself!), and then we mark off the remaining multiples, by jumping in steps of $p$ until we fall off the interval $[a,b]$.
• @mac07 isprime is indexed with position 0 corresponding to n, position 1 corresponding to n+1, etc. That's why it's okay for it to have a static size of 100,001; the problem statement guarantees that m-n is no more than 100,000, so the index corresponding to m must be somewhere in the array. – hobbs Oct 2 '16 at 5:01