我要招人

去企业版

首页 > 试题广场 >

质因数的个数

[编程题]质因数的个数

热度指数：50506 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

牛客665343024号

#include <stdio.h>

int main() {

int i, n;

int num=1;

scanf("%d",&n);

for (int i=2; i<n; i++) {

while (i) {

if (n%i == 0) {

n=n/i;

num++;

}

else {

break;

}

printf("%d",num);

return 0;

}

编辑于 2024-03-23 14:22:55 回复(0)

牛客45001510号

#include <stdio.h>
#include<math.h>
int main() {
    int num;
    while (scanf("%d", &num) != EOF) { 
    int kai,i,count = 0,flag = 0;
     kai = (int)sqrt(num);
     if(kai*kai == num){num = (int)sqrt(num);flag = 1;}
    for(i = 2;num != 1;i++){
        if(num % i == 0){
            count++;
            num /= i;
            i = 1;
        }
    }
    if(flag == 1){count *= 2;}
        printf("%d\n", count);
    }
    return 0;
}

//不要写子函数，够运行的

编辑于 2023-12-19 16:56:27 回复(0)

顶呱呱的火龙果很不想上网课

#include <stdio.h>
#include <math.h>

int main(){
    int x, count = 0, n;
    scanf("%d", &x);
    n = sqrt(x);
    for (int i = 2; i <= n; i ++) {
        while (x%i==0) {
            count ++;
            x/=i;
        }
        if (x==1) {
            break;
        }
    }
    if (x>1) {
        count ++;
    }
    printf("%d\n", count);
    return 0;
}

发表于 2023-02-14 11:45:24 回复(0)

牛客328233386号

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 40000
//判断一个数是否是质数
int panduan(int n){
	int i;
	if(n<2) return 0;
	for(i=2;i<=sqrt(n);i++){
		if(n%i==0)
		return 0;
	}
	return 1;
}
//筛法求出一段区间内的所有质数 
int zhishu(int high,int *a){
	int i,j=0,k=2;
	int *visit;
	visit=(int*)malloc(sizeof(int)*(high+1));
	for(i=0;i<=high;i++)
	visit[i]=0; 
	visit[0]=1;visit[1]=1;
	for(i=2;i<=high;i++){
		if(visit[i])
		continue;
		if(panduan(i)){
			a[j++]=i;
		}
		while(k*i<=high){
				visit[k*i]=1;
				k++;
			}
			k=2;
	}
	return j;
}
int main(){
	int a[max];
	int z,n,k=0;
	int answer=0;
	z=zhishu(max,a);
	while(scanf("%d",&n)!=EOF){
		while(k<z&&n!=1){
			if(n%a[k]==0){
				answer++;
				n=n/a[k];
			}
			else{
				k++;
			}
		}
        if(n>1) answer++;
		printf("%d\n",answer);
		k=0,answer=0;
	}
}

发表于 2022-03-03 15:53:05 回复(0)

牛客213510968号

#include <stdio.h>
#include <stdlib.h>

int zhiyinshu(int i)
{
if(i==2)
{
return 1;
}else{
for(int j=2;j<i;j++)
{
if(i%j==0){
return zhiyinshu(j)+zhiyinshu(i/j);
break;
}
}
return 1;
}
}

int main()
{
int i;
while(scanf("%d",&i)!=EOF)
{
printf("%d\n",zhiyinshu(i));
}
return 0;

}

//写了个递归的，怎么搞了700多ms，大佬看看还有没有可优化的地方

发表于 2022-01-23 11:14:14 回复(0)

Trenchy

#include <stdio.h>

int count(unsigned int x){
int c=0;
for(unsigned int i=2;(i*i)<=x;i++){
if(x%i==0){
c=count(i)+count(x/i);
break;
}
}
if(c==0) return 1;
else return c;
}

int main(){
unsigned int n;
int c;
while(scanf("%u",&n)!=EOF){
c=count(n);
printf("%d",c);
}
}

发表于 2022-01-22 09:39:35 回复(0)