/* http://projecteuler.net/
 *
 * Problem 47
 * Find the first four consecutive integers to have four distinct primes
 * factors. What is the first of these numbers?
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>

using namespace std;

const int max_num = 44722; // sqrt(2000000000)

bitset<max_num> sieve;
vector<int> primes;

void generate_primes() {
    sieve.set();
    sieve.reset(0);
    sieve.reset(1);

    for (int i = 2; i*i < max_num; ++i)
	if (sieve[i])
	    for (int j = i+i; j < max_num; j += i)
		sieve.reset(j);
    primes.push_back(2);
    for (int i = 3; i < max_num; i += 2)
	if (sieve[i])
	    primes.push_back(i);
}

// complexity is my name for the number of distinct prime factors
int complexity(int n) {
    int result = 0, root = static_cast<int>(sqrt(n))+1;
    for (int i = 0; n>1 && i<primes.size() && primes[i]<=root; ++i)
	if (n % primes[i] == 0) {
	    ++result;
	    while (n % primes[i] == 0)
		n /= primes[i];
	}
    if (n>1)
	++result;
    return result;
}

int main() {
    generate_primes();

    // A few tests for complexity()
    //cout << "14 : " << complexity(14) << endl;
    //cout << "20 : " << complexity(20) << endl;
    //cout << "100 : " << complexity(100) << endl;
    //cout << "101 : " << complexity(101) << endl;
    //cout << "9699690 : " << complexity(9699690) << endl;

    int x, found = 0;
    for (x = 2; x+3 < 2000000000 && found < 4; ++x)
	if (complexity(x) == 4)
	    ++found;
	else
	    found = 0;
    cout << x-4 << endl;

    return 0;
}