（蓝桥杯质因数个数）为什么i可以<=n/i，为什么最后n>1时ans还要++

*
问题描述
给定正整数 n, 请问有多少个质数是 n 的约数。
输入格式
输入的第一行包含一个整数 n 。
输出格式
输出一个整数, 表示 n 的质数约数个数。
*/

```c++
#include 
#include
using namespace std;
int main()
{
  
    long long n=0;
    int ans=0;
    scanf("%lld",&n);
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            ans++;
            while(n%i==0)
            n/=i;
        }
    }
    if(n>1)
    ans++;
    printf("%d\n",ans);
  return 0;
}

```

因为最大的因数不能超过根号下n。一个比根号n还大的数，必然相乘的另一个因数小于根号n，那么已经判断过了
这么写可以略微快一点点。

i<=n/i，相当于i*i<=n

• 关于该问题，我找了一篇非常好的博客，你可以看看是否有帮助，链接：已知数组A[n]的元素为整型，设计算法将其调整为两部分，左边所有元素为奇数，右边所有元素为偶数。
• 除此之外, 这篇博客: 牛客寒假算法基础集训营6补题和题解中的 还有一种贪心方式 那就是输入的同时判断能不能吃，只要能吃就吃下去，加上刚输入的a[i]的数量/2就是最多能吃的，再让它对2取余，如果还剩下1就可以继续和下一个吃，如果不行就直接让ans+=a[i]/2 这就是吃的最多的方案 代码： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #include<bits/stdc++.h>
  using namespace std;
  long long ans;
  int a[100010];
  int main()
  {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      if(a[i-1]==1&&a[i]>=1)
      {
        a[i-1]--;
        a[i]--;
        ans++;
      }
      ans+=a[i]/2;
      a[i]%=2;
    }
    cout<<ans;
  }