Divisor Subtraction

Description

You are given an integer number nn. The following algorithm is applied to it:

  1. if n=0, then end algorithm;
  2. find the smallest prime divisor d of n;
  3. subtract dd from n and go to step 1.

Determine the number of subtrations the algorithm will make.

Input

The only line contains a single integer nn (2≤n≤10^10).

Output

Print a single integer — the number of subtractions the algorithm will make.

Sample Input

Input
5
Output
1
Input
4
Output
2

Hint

In the first example 5 is the smallest prime divisor, thus it gets subtracted right away to make a 0.

In the second example 2 is the smallest prime divisor at both steps.

题解：给你一个数n，找它的最小素因子，每回减去，直到n=0，素因子均为奇数（除了2），奇-奇=偶，例如15，标准答案应该为7而不是5，在1e5内没有素因子时，答案为1。

代码如下：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<string>
 7 #include<vector>
 8 #include<cmath>
 9 #include<stack>
10 #include<queue>
11 #include<map>
12 #include<set>
13 #define memset(x,y) memset(x,y,sizeof(x))
14 #define swap(a,b)  (a=a+b,b=a-b,a=a-b)
15 #define debug(x) cout<<x<<" "<<endl
16 #define rson i << 1 | 1,m + 1,r
17 #define e  2.718281828459045
18 #define max(a,b)   (a>b?a:b)
19 #define min(a,b)   (a<b?a:b)
20 #define read(x) scanf("%d",&x)
21 #define put(x) printf("%d\n",x)
22 #define lowbit(x) (x&(-x))
23 #define lson i << 1,l,m
24 #define INF 0x3f3f3f3f
25 #define ll long long
26 #define mod 1001113
27 #define N 100000000
28 #define PI acos(-1)
29 #define eps 1.0e-6
30 #define maxn 27
31 //std::ios::sync_with_stdio(false);
32 //cin.tie(NULL);
33 //const int maxn=;
34 using namespace std;
35 
36 
37 
38 int main()
39 {
40     ll n;
41     cin>>n;
42     for(ll i=2;i*i<=n;i++)
43     {
44         if(n%i==0)
45         {
46             cout<<1+(n-i)/2<<endl;
47             return 0;
48         }
49     }
50     cout<<"1"<<endl;
51     return 0;
52 }

 

版权声明：本文为baiyi-destroyer原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/baiyi-destroyer/p/10085453.html