题目1207：质因数的个数-白红宇

题目1207：质因数的个数

阅读量：4361 次

发布时间：2019-06-07

本文共 1231 字，大约阅读时间需要 4 分钟。

题目1207：质因数的个数

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：1397

解决：326

题目描述：

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

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

输入：

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

算法:

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

代码:

View Code

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #include
                   
                    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; }