B. Divisor Subtraction

B. Divisor Subtraction

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer number n

. The following algorithm is applied to it:

1. if n=0

• , then end algorithm;
• find the smallest prime divisor d
• of n
• ;
• subtract d
• from n and go to step 1

  Determine the number of subtrations the algorithm will make.

  Input

  The only line contains a single integer n

  (2≤n≤1010

  ).

  Output

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

  Examples

  Input

  Copy

  5
  

  Output

  Copy

  1
  

  Input

  Copy

  4
  

  Output

  Copy

  2
  

  Note

  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，和一个算法，求这个算法能执行多少次。算法内容：

  1. 如果n等于0，算法结束。

  2. 找到n最小的素数因子d

  3. n-=d，之后回到步骤1

• 分析：对于输入的n有3种情况：

  1. 素数-------------输出1

  2. 偶数-------------输出n/2

  3. 奇数或合数-------------减去最小的素因子，变为偶数，再执行偶数的计算方法并加1

• #include <iostream>
  #include <cstdio>
  #include <cstdlib>
  #include <string>
  #include <cstring>
  #include <algorithm>
  #include <cmath>
  using namespace std;
  
  bool IsPrime(long long num)	//num为我们要判断的数
  {
  	for (long long i = 2; i <= sqrt(num); i++)		//最优化的判断方式
  	{
  		if (num%i == 0)
  		{
  			return false;
  		}
  	}
  	return true;
  }
  long long fi(long long n){
      for(long long i = 2;i < n;i++){
          if(n % i == 0)
              return i;
      }
  }
  
  int main()
  {
      long long n;
      while(cin>>n){
          long long t = 0;
          if(n % 2 == 0)
              cout<<n/2<<endl;
          else{
              if(IsPrime(n))
                  cout<<1<<endl;
              else{
                  t = n-fi(n);
                  cout<<t/2+1<<endl;
              }
          }
      }
      return 0;
  }