1
$\begingroup$

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.

$\endgroup$

closed as off-topic by David Richerby, Evil, Tom van der Zanden, Juho, Thomas Klimpel Oct 17 '16 at 22:08

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – Tom van der Zanden, Thomas Klimpel
  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, Evil, Juho
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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]$.

$\endgroup$
  • $\begingroup$ Thanks for answering. To be specific I'm not able to digest the lines containing "isprime[j - M]" and "isprime[i-M]" . I'm not getting any pattern here. I already spent like a whole week on this. I could see that the last for loop checks the array isprime starting from even index 0,2,4....till the last even index less than b for interval [a,b] where a is odd and again it checks from inde 1,3,5.....till last odd indexless than b for even a. Can you elaborate please? Can try proof by induction here? $\endgroup$ – mac07 Sep 30 '16 at 13:25
  • $\begingroup$ My answer contains almost all the details needed to understand the code. The remaining details you should be able to work out on your own. $\endgroup$ – Yuval Filmus Sep 30 '16 at 13:46
  • $\begingroup$ I agree and I can't expect anymore than that. I went step by step this time using pen and paper again which really helped. The way marking is done is same as the way the last loop checks whether that particular number between [a,b] is prime or not using the difference for index. Now I realize why you said work out on your own. Thank you very much. $\endgroup$ – mac07 Sep 30 '16 at 15:36
  • $\begingroup$ @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. $\endgroup$ – hobbs Oct 2 '16 at 5:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.