#include "stdafx.h"
#include <cmath>
#include <iostream>

long long isPrime(long long num) {
  long long max = (long long) sqrt((long double) num);
  for (long long i = 2; i <= max; i++) {
    if (num % i == 0) return 0;
  }
  return 1;
}

long long n3 (long long num) {
  if (isPrime(num)) return num;
  long long max = num / 2;
  for (long long i = 2; i <= max; i++) {
    if (num % i == 0 && isPrime(num / i))
      return num / i;
  }
  return num;
}



int main() {
  long long test = 523456789;
  for (long long i = test; i < test + 100; i++)
    std::cout << i << ": " << n3(i) << std::endl;
  //system("pause");
  return 0;
}