首页 > ACM题库 > 九度OJ > 九度-1207-质因数的个数[解题代码]
2013
12-13

九度-1207-质因数的个数[解题代码]

题目来源:2007年清华大学计算机研究生机试真题

题目描述:
求正整数N(N>1)的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。
输入:

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

输出:

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

样例输入:
120
样例输出:
5
提示:

注意:1不是N的质因数;若N为质数,N是N的质因数。


cpp 代码如下:
#include <stdio.h>
#include <math.h>
int main() {
		long long n;
		while(scanf("%lld",&n) != EOF){
			int m = sqrt(n);
			int count = 0;
			while(n>1){
				int i;
				for(i=2; i<=m; i++){
					if(n%i == 0){
						count ++;
						n /= i;
						break;
					}
				}
				if(i == m+1 && n>1){
					count ++;
					break;
				}
			}
			printf("%d\n",count);

		}

return 0;
}
/**************************************************************
	Problem: 1207
	User: coder
	Language: C
	Result: Accepted
	Time:20 ms
	Memory:920 kb
****************************************************************/

java 代码如下:

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
	static long n;
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextLong()){
			n = s.nextLong();
			int m = (int) Math.sqrt(n);
			int count = 0;
			while(n>1){
				int i;
				for(i=2; i<=m; i++){
					if(n%i == 0){
						count ++;
						n /= i;
						break;
					}
				}
				if(i == m+1 && n>1){
					count ++;
					break;
				}
			}
			System.out.println(count);
			
		}
	}

}
/**************************************************************
	Problem: 1207
	User: coder
	Language: Java
	Result: Accepted
	Time:240 ms
	Memory:18800 kb
****************************************************************/


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.