思路

观察一下可以知道一个数最大操作数也就是logn次 ，发现n最大只有10^12，暴力判断一次素数则需要10^6，且判断的越来越快，o(sqrt(n)*logn)满足时间复杂度

代码如下

cpp

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

// 判断是否为素数的函数
bool isPrime(long long n) {

题目内容

塔塔现在有$n$颗糖果。他有一个吃糖果的计划。

具体是:如果剩余的糖果数量是素数，那么这天他会吃[$n/3$]$+1$颗。否则这天就吃[$n/2$]$+1$颗。问

他的糖果可以吃几天。[$x$]:表示对$x$向下取整。例如:[$1.90$]=$1$。

输入描述

输入一个整数$n$($1≤n≤10^{12}$),表示游游的糖果数量。

输出描述

输出一个整数，表示塔塔可以吃的天数。

样例1

输入

10

输出

3