首页 > 试题广场 >

质因数的个数

[编程题]质因数的个数

热度指数：50129 时间限制：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

输入

输出

算法知识视频讲解

sunX&Y

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5;
int primes[maxn+5];   //素数表
bool isPrime[maxn+5];
int cnt;

void getPrimes()   //线性欧拉筛拿素数表
{
    fill(isPrime, isPrime+maxn, true); 
    isPrime[0] = isPrime[1] = false; cnt = 0; 
    for(int i = 2;i <= maxn; i++)                   
    {
        if(isPrime[i]) primes[cnt++] = i; 
        for(int j = 1;j < cnt && primes[j]*i <= maxn; j++)       
        {
            isPrime[primes[j]*i] = false;
            if(i % primes[j] == 0) break;                  
        }
    }
}

int ansFacts(int n)   //质因子个数
{
    int h = sqrt(n);
    int ans = 0;
    for(int i = 0;primes[i] <= h; i++)
    {
        while(n % primes[i] == 0)
        {
            ans++; n /= primes[i];
        }
        if(n == 1) break;
    }
    if(n > 1) ans++;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    getPrimes();
    while(cin >> n)
    {
        cout << ansFacts(n) << "\n";
    }
    return 0;
}

按部就班来一个一个数。😶

可以根据质因子的性质，直接往下除就可以，可以除尽的一定只能是质数，不需要再开一个专门的素数表。

#include<bits/stdc++.h>

using namespace std;

int getFacts(int n)
{
    int ans = 0;
    int h = sqrt(n);
    for(int i = 2;i <= h; i++)
    {
        while(n % i == 0)
        {
            ans++; n /= i;
        }
        if(n == 1) break;
    }
    if(n > 1) ans++;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        cout << getFacts(n) << "\n";
    }
    return 0;
}

编辑于 2021-01-17 22:28:46 回复(0)

更多回答

C/C++

拜托求求给一个offer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 4e4;
bool arr[MAX];
vector<int> prime;

void initial()
{
    for (int i = 2; i < MAX; i++)
    {
        arr[i] = true;
    }
    for (int i = 2; i < MAX; i++)
    {
        if (!arr[i])
        {
            continue;
        }
        prime.push_back(i);
        for (int j = 2 * i; j < MAX; j += i)
        {
            arr[j] = false;
        }
    }
}

int getNum(int n)
{
    int total = 0;
    for (int i = 0; i < prime.size(); i++)
    {
        if (n < prime[i])
        {
            break;
        }
        int sum = 0;
        while (n % prime[i] == 0)
        {
            sum++;
            n /= prime[i];
        }
        total += sum;
    }
    if (n > 1)
    {
        total++;
    }
    return total;
}

int main()
{
    initial();
    int n;
    while (cin >> n)
    {
        cout << getNum(n) << endl;
    }
    return EXIT_SUCCESS;
}

发表于 2021-02-19 14:20:59 回复(0)

发愤图强的小菜

java版

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);

        while (in.hasNext()) {
            Long n=in.nextLong();
            int count=0;

            for (long i=2;i<=Math.sqrt(n);i++){
                while (n % i == 0) {
                    n/=i;
                    count++;
                }
                if (n<=1)
                    break;
            }
            if (n>1)
                count++;

            System.out.println(count);
        }

        in.close();
    }
}

发表于 2017-07-18 18:27:29 回复(0)

C/C++

|讨厌鬼|

一个分解质因数的程序，不仅可以统计质因数个数，还保存了质因数的数值及其次幂

#include<stdio.h>
#define N 100001
int prime[N];
int primesize;
bool mark[N];
void init(){
    for(int i=0;i<N;i++)
        mark[i]=false;
    primesize=0;
    for(int i=2;i<N;i++){
        if(mark[i]==true) continue;
        else{
            prime[primesize++]=i;
            for(int j=i*i;j<N;j+=i)
                mark[i]=true;
        }
    }
}
int main(){
    init();
    int x;
    while(scanf("%d",&x)!=EOF){
        int ansPrime[30];
        int ansSize=0;
        int ansNum[30]={0};
        for(int i=0;i<primesize;i++){
            if(x%prime[i]==0){
                ansPrime[ansSize]=i;
                ansNum[ansSize]=0;
                while(x%prime[i]==0){
                    ansNum[ansSize]++;
                    x/=prime[i];
                }
                ansSize++;
                if(x==1) break;
            }
        }
        if(x!=1){
            ansPrime[ansSize]=x;
            ansNum[ansSize++]=1;
        }
        int ans=0;
        for(int i=0;i<ansSize;i++)
            ans+=ansNum[i];
        printf("%d\n",ans);
    }
    return 0;
}

发表于 2018-01-15 20:51:02 回复(4)

C++

牛客113649850号

#include<iostream>
#include<vector>

using namespace std;

const int N = 4e4;

vector<int> v;
bool isPrime[N];

void init(){
    fill(isPrime, isPrime + N, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2;i < N;i++){
        if(!isPrime[i]) continue;
        v.push_back(i);
        if(i > N / i) continue;
        for(int j = i * i;j < N;j += i) isPrime[j] = false;
    }
}

int main(){
    int n, i;
    init();
    int total = v.size();
    while(scanf("%d", &n) != EOF){
        int count = 0;
        while(n != 1){
            for(i = 0;i < total;i++){
                if(n % v[i] == 0){
                    count++;
                    break;
                }
            }
            if(i < total) n /= v[i];
            else break;
        }
        if(n == 1)
            printf("%d\n", count);
        else printf("%d\n", count + 1);
    }
    return 0;
}

发表于 2022-01-25 17:11:54 回复(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)

C/C++

PicKuan

#include <iostream>
using namespace std;
int solve(int x){
    for(int i=2;i*i<=x;i++) if(x%i==0) return solve(i)+solve(x/i);
    return 1;
}
int main(){
    int N;
    while(cin>>N) cout<<solve(N)<<endl;
}

dddddddd递归啊兄弟萌

发表于 2020-04-30 10:50:32 回复(0)

C/C++

YhX.

#include<stdio.h>//质因数,不用判断是否为质数
int main()
{
    int N,i,num;
    scanf("%d",&N);
    num=0;
    for (i=2;i*i<=N;i++)//i*i节省运行时间
    {
        while (N%i==0)//因数
        {
            N/=i;
            num++;
        }
    }
    if(N!=1) num++;
    printf("%d",num);
    return 0;
}

发表于 2020-03-21 16:20:13 回复(0)

Java

LHC0512

Java 解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int i = scanner.nextInt();
            int count=0;
            for (int j = 2; j*j<=i ; j++) {
                while (i%j==0){
                    i/=j;
                    count++;
                }
            }
            if (i>1) count++;
            System.out.println(count);
        }
    }
}

编辑于 2020-03-17 16:04:23 回复(0)

从前的日子变得慢

写一个判断一个数是否为质数的函数，用数组prime[ ]把5000以内的质数按从小到大的顺序存储起来。
输入N，判断N是否为质数，如果是进入循环，用N除以prime[i]，如果能整除，sum++，N=N/prime[i],否则把除数换成prime[i++] 。
N为质数时退出循环，输出sum。

#include<iostream>
(720)#include<cmath>
using namespace std;
bool isPrime(int n){
	bool flag=true;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			flag=false;
			break;
		}
	} 
	return flag;
}

int main(){
    int j=0,prime[1000];//求5000以内的所有质数 
	for(int i=2;i<5000;i++){
		if(isPrime(i)){
			prime[j]=i;
			j++;
		}
	}
	int N;
	while(cin>>N){
		int sum=1;
		int i=0;
		while(!isPrime(N)){
			if(N%prime[i]==0){
				sum++;
				N=N/prime[i];
			}
			else{
				i++;
			}
			
		}
		cout<<sum<<endl;
	
	} 
	return 0;
}

发表于 2020-03-14 11:41:10 回复(0)

C/C++

奔跑的牛阿牛

质因数可以重复使用这点挺关键的，每次被质因数整除完，继续被相同质因数整除，直到整除不了再往下走

//感觉以前好像没学过分解质因数诶，应该是没好好学吧T_T;
#include<iostream>
using namespace std;

int NumberOfPrime(int x){
    int number = 0;
    for(int i=2; i*i<=x; i++){
        if(x%i==0){
            number++;
            x /= i;
            i--;
        }
    }
    number++;
    return number;
}
int main(){
    int N;
    while(cin>>N){
        cout<<NumberOfPrime(N)<<endl;
    }
    return 0;
}

发表于 2020-02-26 23:32:31 回复(0)

陆小陆20190403151627

#include<iostream>
#include<cmath>
using namespace std;
int digui(int num)
{
 int count = 0,i;
 for(i=2;i<=sqrt(num);i++)
 {
  if(num%i==0)
  {//i一定是一个小质数 
   count++; 
   count+= digui(num/i); 
   break;
  }
 }
 if(count==0)//说明是一个质数，count加1
  count++;
 return count;
}
int main()
{
 int num;
 cin>>num;
 cout<<digui(num); 
}

递归求解

发表于 2019-04-09 17:32:10 回复(0)

NeuralNetwork

#include <stdio.h>
#include <stdbool.h>

unsigned int getPrimeFactor(unsigned long n)
{// 返回n代表形参为质数 
    //此函数正常返回值为最小的质因数
    for(unsigned long i = 2; i * i < n; ++i)
    {
        if(n % i == 0)
            return i;
    }
    return n;
}

int main(void)
{
    unsigned long num;
    int count = 0;
    while(scanf("%ld", &num) != EOF)
    {
        unsigned int factor;
        bool flag = false;
        while( (factor = getPrimeFactor(num)) != num)
        {
            flag = true;
            count ++;
            num /= factor;
        }
        if(flag == true)
            count ++;
         printf("%d\n", count);
    }
}

发表于 2019-03-08 01:33:52 回复(0)

Python

TimeMac

while True:
    try:
        num = int(input())
        result = 0
        while num >2:
            for i in range(2,int(num**0.5)+1):
                if num % i == 0:
                    result+=1
                    num//=i
                    break
            else:          #这个表示for循环全跑完执行的，相当于此时num为质数
                result+=1
                break
        print(result)
    except Exception:
        break

编辑于 2018-10-11 17:05:08 回复(0)

牛客吴彦祖QAQ

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
bool isPrime(int n)
{
    if(n == 1)//1不是质数，但是为了循环结束条件逻辑一致
        return true;
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
int main()
{
    vector<int> prime;
    for(int i = 2; i <= 10000; i++)
    {
        if(isPrime(i))
            prime.push_back(i);
    }
    int ret = 1;
    int index = 0;
    int num;
    cin >> num;
    while(!isPrime(num))
    {
        if(num % prime[index] == 0)
        {
            num = num / prime[index];
            ret++;
        }
        else
            index++;
     }
    cout << ret << endl;
    return 0;
}

发表于 2018-07-24 20:47:18 回复(0)

倩倩爱帷帷

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int count=0;
        for(int i = 2;i <= n;i++){
            while(n % i == 0){
                count++;
                n = n / i;
            }
        }
        System.out.println(count);
    }

}

发表于 2018-03-29 10:49:34 回复(0)

时光是影子的眼

//王道简化版解法
#include<stdio.h>
#include<math.h>
int prime[100000];
int primeSize = 0;
bool mark[100000] = { 0 };
void init() {
    for (int i = 2; i <= 100000; i++) {
        if (mark[i] == 0) {
            prime[primeSize++] = i;
            if (i <= 1000) {
                for (int j = i * i; j<100000; j += i)
                {
                    mark[j] = true;
                }
            }
        }
    }
}
int main() {
    init();
    int n;
    while (scanf("%d", &n) != EOF) {
        int count = 0, i = 0;
        while (n != 1 && i < primeSize) {
            if (n%prime[i] == 0) {
                count++;
                n /= prime[i];
            }
            else i++;
        }
        if (n != 1) {
            count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

发表于 2018-03-06 16:35:01 回复(3)

C/C++

成程晨

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

发表于 2018-01-13 16:51:47 回复(2)

梅老板的粉

/*
此题是一道大数分解的题目，可以直接递归调用方法进行分解
*/
#include<vector>
#include<iostream>
#include<cmath>
using namespace std;
//getFactor对num进行分解，将分解后的数放到vec中
void getFactor(const int& num, vector<int>& vec)
{
	if (num == 1)//不需要分解，直接返回
		return;
	int x = sqrt(num) + 1;
	int i = 2;
	for (i; i < x; ++i)
	{
		if (num%i == 0)
			break;
	}
	if (i == x)
		vec.push_back(num);//判断为质数，直接放入vec中
	else//若不为质数，则继续进行分解
	{
		getFactor(i, vec);
		getFactor(num / i, vec);
	}
}
int main()
{
	int num;
	vector<int> rslt;
	while (cin >> num)
	{
		vector<int> vec;
		getFactor(num, vec);
		rslt.push_back(vec.size());
	}
	for (auto&e : rslt)
		cout << e << endl;
}

编辑于 2017-04-21 16:22:17 回复(0)

grower

#include <iostream>
#include <math.h>
using namespace std;
int main()
    {
    int n;
    int count = 0;
    while(cin >> n)
        {
        count = 0;
        int i = 2;
        int m = n;
        while(i <= sqrt(n))
            {
            while(n % i == 0)
             {
                n = n / i;
                count++;
                if(n == 1)
                    break;
            }
            i++;
        }
       if(n > sqrt(n))//考虑n是否存在大于sqrt(n)的质因数，如果存在，最多存在一个，因为两个大于sqrt(n)的数相乘大于n
            count++;
        cout << count << endl;

}
}

发表于 2016-04-16 21:44:47 回复(0)