module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.math;
import std.stdio;
import std.string;

struct Input
{
	ulong n;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
		n = readln().strip().to!ulong;
	}
}

struct Output
{
}

auto main2(Input* input)
{
    struct PrimeInfo
    {
        ulong prime;
        ulong count;
    }

    PrimeInfo[] primes;
    PrimeInfo first = {2,0};
    primes ~= first;

    bool isPrime(ulong n)
	{
		auto r = floor(sqrt(cast(real)n));
		foreach (p; primes)
		{
			if (p.prime > r)
				return true;

			if (n % p.prime == 0)
				return false;
		}
		return true;
	}

    auto temp = input.n;

    while (true)
    {
        if (temp % 2 == 0)
        {
            primes[$-1].count++;
            temp /= 2;
        }
        else
        {
            break;
        }
    }

    for (ulong n = 3; temp != 1; n+=2)
    {
        if (isPrime(n))
        {
            PrimeInfo pi = {n,0};
            primes ~= pi;

            if (n > sqrt(floor(cast(real)temp)))
                break;

            while (true)
            {
                if (temp % n == 0)
                {
                    primes[$-1].count++;
                    temp /= n;
                }
                else
                {
                    break;
                }
            }
        }
    }

    if (temp != 1)
    {
        PrimeInfo pi = {temp, 1};
        primes ~= pi;
    }

    ulong[] counts;
    counts.length = primes.length;

    ulong max = 1;
    ulong r = cast(ulong)(sqrt(cast(real)input.n));

    LOOP:
    while (true)
    {
        foreach (i, ref c; counts)
        {
            if (c < primes[i].count)
            {
                c++;
                break;
            }
            else
            {
                c = 0;
                if (i == counts.length - 1)
                    break LOOP;
            }
        }

        auto mul = 1;
        foreach (i, c; counts)
        {
            mul *= primes[i].prime ^^ c;
        }

        if (mul <= r && mul > max)
            max = mul;
    }

    return (max - 1) + (input.n / max - 1);
}

unittest { writeln("begin unittest"); }

unittest // example1
{
	string example =
`10`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 5);
}

unittest // example2
{
	string example =
`50`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 13);
}

unittest // example3
{
	string example =
`10000000019`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 10000000018);
}

unittest { writeln("end unittest"); }

void parseExample(out Input input, string example)
{
	struct Adapter
	{
		string[] _lines;
		this(string input) { _lines = input.splitLines(); }
		string readln() { auto line = _lines[0]; _lines = _lines[1..$]; return line; }
	}
	parseInput(input, Adapter(example));
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	auto result = main2(&input);
	writeln(result);
}


Measured memory_bytes: 3964