1076B Divisor Subtraction

缺乏、安全感 2022-04-17 04:40 130阅读 0赞

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 nn. The following algorithm is applied to it:

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

Determine the number of subtrations the algorithm will make.

Input

The only line contains a single integer nn (2≤n≤10102≤n≤1010).

Output

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

Examples

input

Copy

output

Copy

input

Copy

output

Copy

Note

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

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

**题意：给出一个数n，找出最小质因子，然后n-减去这个质因子，无限次这种循环直到n=0，求出一共需要进行多少次。**

**题解：我的方法是先线性筛，筛出1e5内的质因子，然后看n没有质因子，有的话**，**就要分三种情况，****一种是奇数减去第一次质因子后，变成偶数了****，以后的质因子都是2了，不再是3，例如15，质因子为3，减去后为12，所以最终答案是7不是5。一种是：质因子就是本身的例如5，就是n/质因子，严格来说就是两种，但是n的范围很大1e10，线性筛，筛不完，所以要特判，如果在1e5内没有质因子，就是答案就是1，（因为质因子就是本身，第二种情况）**

c++：

#include<bits/stdc++.h>
    using namespace std;
    int vis[100000];
    int a[100010],cnt;
    void Init()
    {
        memset(vis,0,sizeof(vis));
        int i,j;
        for(i=2; i<100000; i++)
        {
            if(!vis[i])
            {
                a[cnt++]=i;
                for(j=i+i; j<100000; j+=i)
                {
                    vis[j]=1;
                }
            }
        }
    }
    int main()
    {
        Init();///线性筛模版
        long long n,ans=0;
        cin>>n;
        for(int i=0; i<cnt; i++)
            if(n%a[i]==0&&(n-a[i])%2==0)
            {
                cout<<(n-a[i])/2+1<<endl;
                return 0;
            }
            else if(n%a[i]==0)
            {
                cout<<n/a[i]<<endl;
                return 0;
            }
      cout<<1<<endl;
        return 0;
    }

还有大神的简短代码：c++：

#include <stdio.h>
    #include <vector>
    int main()
    {
    	long long n,i,i2;
    	scanf("%I64d",&n);
    	for(i=2;i*i<=n;i++)
    	{
    		if(n%i==0)
    		{
    			printf("%I64d",1+(n-i)/2);
    			return 0;
    		}
    	}
    	printf("%d",1);
    	return 0;
    }

python：

n=int(input())
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            print(1+(n-i)//2)
            exit()
    print(1)