JWoC_Algorithms/minDifference.cpp at master · JGEC-Winter-of-Code/JWoC_Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <bits/stdc++.h>
using namespace std;

const int sz = 1e5;
bool isPrime[sz + 1];

void sieve()
{
	memset(isPrime, true, sizeof(isPrime));

	isPrime[0] = isPrime[1] = false;

	for (int i = 2; i * i <= sz; i++) {
		if (isPrime[i]) {
			for (int j = i * i; j < sz; j += i) {
				isPrime[j] = false;
			}
		}
	}
}
int minDifference(int L, int R)
{

	int fst = 0;
	for (int i = L; i <= R; i++) {

		if (isPrime[i]) {
			fst = i;
			break;
		}
	}
	int snd = 0;
	for (int i = fst + 1; i <= R; i++) {

		if (isPrime[i]) {
			snd = i;
			break;
		}
	}
	if (snd == 0)
		return -1;

	int diff = snd - fst;

	int left = snd + 1;
	int right = R;

	for (int i = left; i <= right; i++) {

		if (isPrime[i]) {

			if (i - snd <= diff) {

				fst = snd;
				snd = i;
				diff = snd - fst;
			}
		}
	}

	return diff;
}

int main()
{
	sieve();

	int L = 21, R = 50;

	cout << minDifference(L, R);

	return 0;
}