题目1207：质因数的个数

喜欢ヅ旅行 2021-10-23 11:56 365阅读 0赞

题目1207：质因数的个数

**时间限制：**1 秒

**内存限制：**32 兆

**特殊判题：**否

**提交：**1397

**解决：**326

**题目描述：**

求正整数N(N>1)的质因数的个数。

相同的质因数需要重复计算。如120=2\*2\*2\*3\*5，共有5个质因数。

**输入：**

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

算法:

只要筛选出sqrt(1000000000)前面的素数即可。

代码:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    
    int n, a, cnt;
    int prime[41000];
    int hash[41100]={
             0};
    int visit[41100];
    
    void Get_Prime( )
    {
      cnt = 0;
      int x = (int)sqrt(1000000000.0);
      int y = (int)sqrt( x * 1.0 );
      for( int i = 2; i <= y; i++)
      {
        if( !hash[i] )
        {
          for( int j = i + i; j <= 31630; j += i )
               hash[j] = 1;    
            
        }     
      }
      for( int i = 2; i <= 31630; i++)
           if( !hash[i] )
               prime[cnt++] = i;     
    }
    
    void Get_Fac( int x)
    {
      int id = 0, ans = 0;
      while( x )
      {
          while( x % prime[id] == 0 && x!= 1)
                 x /= prime[id], ans++;    
          id++;   
          if( x == 1)
              break;
          if( id >= cnt )
          {
             ans++;
             break;    
          }   
      }
      printf("%d\n",ans);
         
    }
     
    
    
    int main( )
    {
      Get_Prime( );
      while( scanf("%d",&n) != EOF)
      {
         memset(hash,0,sizeof(hash));
         Get_Fac(n);       
      }
      return 0;  
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/21/2649628.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/c49034b7516143ff9dc8d6118f2eb7c6.png