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

1.分解质因数

质因数个数

题目描述

Time Limit: 1000 ms

Memory Limit: 32768 mb 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。

输入描述:

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

输出描述:

对于每组数据，输出N的质因数的个数。

代码

#include 
   
    using namespace std;const int maxn = 1000000+5;int prime[maxn];void getPrim(){
   	memset(prime,0,sizeof(prime));	for(int i = 2;i<=maxn;i++){
   		if(!prime[i])				prime[++prime[0]] = i;		for(int j =  1;j<=maxn&&prime[j]*i<=maxn;j++){
   			prime[prime[j]*i] = 1;			if(i%prime[j]==0)	break;		}	}}int main(){
   	getPrim();	int n;	while (scanf("%d",&n)!=EOF){
   		int ans = 0;		for(int i = 1;i
    
     1) ans++;		printf("%d\n",ans);	}	return 0;}
    
   

整除问题

题目描述

Time Limit: 1000 ms

Memory Limit: 256 mb 给定n，a求最大的k，使n！可以被a^ k整除但不能被a^(k+1)整除。

输入描述:

两个整数n(2<=n<=1000)，a(2<=a<=1000)

输出描述:

一个整数.

思路

这个题首先如果数字小的话是可以考虑轮流试的，但是1000的数字范围无论是对阶乘还是幂都太大了。于是我们想一下，既然要求整除，说明每个素因子都是可以抵消的，这样我们就可以求解了。但是还要考虑到，因为后面是求哪个k，所以说我们不是对n!和a的幂分别求出对应的素数因子数组。我采取的方法是这样的：

1、分解得到n!的素数数组。 2、求出a的素数数组 3、求两者的商去最小值

代码

在这里插入代码片

2.

转载地址：http://hpzsi.baihongyu.com/