#P1807. 2024.4.8-ali-第一题-塔子哥的平方数

2024.4.8-ali-第一题-塔子哥的平方数

题目描述

塔子哥拿到一个整数xx，并希望通过如下两个操作将xx变为完全平方数。

  1. 如xx是素数，则将其减1
  2. 否则，将其除以自己最小的素因子。

塔子哥需要操作多少次？

输入描述

一个正整数xx

1≤x≤1091\le x\le 10^9

输出描述

一个整数，表示操作次数。

样例

输入

5

输出

1

输入

20

输出

3

知识点:*****

查看知识点以及同类型题目

Statistics