因子个数__牛客网

C/C++

兰州小红鸡

#include <iostream>
#include<math.h>
using namespace std;
int main(){
    int n,k,i;
    while(cin>>n){  k=0;
    for(i=2;i<=sqrt(n);i++)
    if(n%i==0){
        while(n%i==0)n=n/i;
        k++; }
    if(n!=1)k++;
    cout<<k<<endl;
    }
    return0;
}

编辑于 2019-03-27 12:52:29 回复(0)

SKT.RUO

#include<stdio.h>
int main()
{
	int x, num, flag, pri[] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 };
	while (~scanf("%d", &x))
	{
		num = 0;
		for (int i = 0;i < 168;i++)
		{
			flag = 0;
			while (x%pri[i] == 0)
			{
				if (x%pri[i] == 0)
					x /= pri[i];
				flag = 1;
			}
			if (flag)
				num++;
		}
		if (x > 1)
			num++;
		printf("%d\n", num);
	}
	return 0;
}

发表于 2017-08-04 14:04:55 回复(2)

Java

来学习的小张

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int count = 0;
            for(int i = 2;i <= Math.sqrt(n);i++){
                if(n % i == 0){
                    while(n % i == 0){
                        n /= i;
                    } 
                  count++;                   
                }
            }
            if(n != 1){
                count++;
            }
            System.out.println(count);
        }
    }
}

发表于 2022-05-07 09:00:14 回复(0)

C/C++

WZ_Dale

从最小因子2到数字的最大因子数（数字的平方根）开始判断是否能够取余

可以则循环取余直到取余不为0，因子个数+1；否则使用下一个因子计算；

最终整除了各个因子数之后剩余的数字不为1则本身也是一个因子，因此因子数+1

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n,k,i;
    while(cin >> n){
        k=0;
        for(i = 2; i <= sqrt(n); i++){
            if(n % i == 0){
                while(n % i == 0){
                    n = n / i;
                }
                ++k;
            }
        }
        if(n != 1){
            ++k;
        }
        cout << k << endl;
    }
    return 0;
}

发表于 2020-07-17 15:55:25 回复(1)

C/C++

hanjiangxue

题目应该叫质因子的个数，太不严谨了，哈哈，不过本来牛客上的就不严谨

#include <cstdio>
(802)#include <cmath>

struct factor{
    int x;
    int cnt;
}fac[10];

const  int MAXN = 100010;
int prime[MAXN], pNum = 0;
bool p[MAXN] = {false};

void findPrime(){
    for (int i = 2; i < MAXN; ++i) {
        if(p[i] == false){
            prime[pNum++] = i;
            for (int j = i + i; j < MAXN; j += i) {
                p[j] = true;
            }
        }
    }
}

int main(int argc, char const *argv[]){
    findPrime();
    int n;
    while(scanf("%d", &n) != EOF){
        int num = 0;//不同质因子的个数
        int sqr = (int)sqrt(n*1.0);
        for (int i = 0; i < pNum && prime[i] <= sqr; ++i) {
            if(n % prime[i] == 0){//如果prime[i]是n的质因子
                fac[num].x = prime[i];
                fac[num].cnt = 0;
                while(n % prime[i] == 0){//计算质因子prime[i]个数
                    fac[num].cnt++;
                    n /= prime[i];
                }
                num++;//不同的质因子个数加1
            }
           if(n == 1) break;
        }
        if(n != 1){
            fac[num].x = n;
            fac[num++].cnt = 1;
        }

        printf("%d\n", num);
    }
    return 0;
}

发表于 2020-03-02 08:55:22 回复(3)

你经历过绝望么丶

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int prime[100005];
void prime_table()
{
    int i,j;
    for(i=2; i<100005; i++)
        if(prime[i]==0)
            for(j=2*i; j<100005; j+=i)
                prime[j] = 1;
}
int main()
{
    int n,t=0;
    int a[20000];
    prime_table();
    for(int i=2; i<100005; i++)
        if(prime[i]==0)
        {
            a[t]=i;
            t++;
        }
    while(~scanf("%d",&n))
    {
        int cnt=0,i=0;
        while(n!=1)
        {
            if(n%a[i]!=0)
                i++;
            else if(n%a[i]==0)
            {
                while(n%a[i]==0)
                    n/=a[i];
                cnt++;
            }
        }
        printf("%d\n",cnt);

    }
}

发表于 2016-10-05 19:43:46 回复(0)

尤鱼哥


//由于先例举出所有的质数表会导致超时，所以决定计算时调用判断质数的函数。
//小技巧是可以判断剩下的数是否为质数，直接结束循环，节约时间。

	





	import java.util.Scanner;



	





	public class Main {



	 public static Boolean isprime(int n) {



	  if (n == 2) {



	   return true;



	  }



	





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



	   if (n % i == 0) {



	    return false;



	   }



	  }



	  return true;



	 }



	





	 public static void main(String[] args) {



	  Scanner in = new Scanner(System.in);



	  while (in.hasNext()) {



	   int count = 0;



	   int n = in.nextInt();



	   if (isprime(n)) {



	    System.out.println(1);



	    continue;



	   }



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



	    if (isprime(i)) {



	     if (n % i == 0) {



	      count++;



	      while (n % i == 0) {



	       n /= i;



	      }



	      if(n==1){



	       System.out.println(count);



	       break;



	      }



	      if(isprime(n)){



	       count++;



	       System.out.println(count);



	       break;



	      }



	     }



	    }



	   }



	





	  }



	





	 }



	





	}

发表于 2016-09-08 13:32:41 回复(0)

啥

贴一个C++递归的

#include <iostream>
#include <stdio.h>

using namespace std;

int cnt;

bool isPrime(int n)
{
    if(n<2) return false;
    if(n == 2) return true;
    if(n%2 == 0) return false;
    for(int i=3; i*i <= n; i+=2) {
        if(n%i == 0) return false;
    }
    return true;
}

void countFactors(int n, int start)
{
    if(isPrime(n)) {
        cnt++; return;
    } else {
        for(int i=start; i<n; i++) {
            if(0 == n%i) {
                cnt++;
                while(0 == n%i) {
                    n /= i;
                }
                countFactors(n, i+1);
                return;
            }
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n)) {
        cnt = 0;
        countFactors(n, 2);
        printf("%d\n", cnt);
    }
    return 0;
}

发表于 2016-01-02 17:24:45 回复(0)

Java

和欣欣一起努力学习

我是利用set自动去重这一特性进行的问题求解，但时间上老是通过不了，通过调试发现是MAIN方法中WHILE循环输入的问题，但是我对其他问题进行求解的时候也是利用WHILE循环解决的多组输入问题就没啥事，有佬可以帮我看看问题出在哪里吗？



	import java.util.Scanner; import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner str = new Scanner(System.in);
        while (str.hasNextInt()){
            int n=str.nextInt();
            System.out.println(soluation(n));
        }
    }

    public static int soluation(int n) {
        TreeSet<Integer> tree = new TreeSet<>();
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                n = n / i;
                tree.add(i);
                 i=2;
            }
        }
        int size= tree.size();
        return size;
    }
}

发表于 2023-11-04 16:58:12 回复(0)

在做测评的卡尔很强大

和上一题一样的思想，注意这里重复因子只算一个，所以把打印换成存入集合就行了，根据集合元素可哈希的特点，利用集合长度就能得出因子个数，但问题是python3用了集合之后会超时，答案是对的，不知道有没有其他解决办法

import math

while 1:
    try:
        n = int(input())
        i = 2
        result = set()
        while i <= math.sqrt(n):
            if n % i == 0:
                result.add(i)
                n = n / i
            else:
                i += 1
        result.add(n)
        print(len(result))
    except:
        break

发表于 2023-05-06 22:13:35 回复(0)

侬是一个好人

暴力，超时

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

void FindDiv(vector<int>& tmp, int n) {
    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0) {
            tmp.push_back(i);
            if(n / i != i){
                tmp.push_back(n / i );
            }
        }
    }
}

bool isPrime(vector<int>& tmp2, int n)
{
    int i = 0;
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    if (i == 2 || i == n) {
        tmp2.push_back(n);
        return true;
    }
    return false;
}

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> tmp1;
        FindDiv(tmp1, n);
        sort(tmp1.begin(), tmp1.end());
        vector<int> tmp2;
        for (int i = 1; i < tmp1.size(); i++)
        {
            isPrime(tmp2, tmp1[i]);
        }
        cout << tmp2.size() << endl;
    }
}

发表于 2023-02-12 16:08:34 回复(0)

满洲里有象&

// write your code here
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int count = 0;
            int num = sc.nextInt();
            for (int i = 2; i < Math.sqrt(num); i++) {
                if(num %i == 0) {
                    while (num % i == 0){
                        num = num/i;
                    }
                    count++;
                }
            }
            if(num == 1) {//说明正好被整除
                System.out.println(count);
            } else {
                System.out.println(++count);
            }
        }
    }
}

发表于 2022-11-17 19:31:17 回复(0)

bug郭

// write your code here
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int x = sc.nextInt();
            int ret = 0;
            // 36 = 2*2*3*3! 因数为 2 !
            //我们以36为例:我们先求出一个因数,
            //然后对该因数相除连续相除自到结果不含该因子时,我们就可以找下一个因子!
            //找到 2  36/2 = 18 18/2 = 9 次数++!
            // 3  9/3 = 3 3/3 = 1   次数++!
            for(int i =2;i<=Math.sqrt(x);i++){
                if(x%i==0){//找到一个因子
                    while(x%i==0){
                        //把相同因子去除!
                        x/=i;
                    }
                   ret++;//次数加1
                }
            }
           if(x!=1){//如果最后x不为 1 说明还有一个因数且是一个素数 !
               ret++;
           }
            System.out.println(ret);
        }
    }
}

发表于 2022-05-13 20:06:30 回复(0)

Java

Lama

思路：一个数的因子就是2 3 5 以及循环整除 2 3 5之后的那个数，我觉得写的没什么问题，对比错误自测能过，但就是过不了，很纳闷。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int a3=0;
            int a2=0;
            int a5=0;
            int aa=0;
            while(a>1){
                if(a%2==0){
                    a=a/2;
                    a2=1;
                }else if(a%3==0){
                    a=a/3;
                    a3=1;
                }else if(a%5==0){
                    a=a/5;
                    a5=1;
                }else{
                    a=a/a;
                    aa=1;
                }
            }
            int ret=a2+a3+a5+aa;
            System.out.println(ret);
        }
    }
}

发表于 2021-07-17 19:39:52 回复(0)

Java

reke

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        while(s.hasNext()){
            int n = s.nextInt();
            int ret = 0;
            // 从2到n的平方根开始遍历因子
            for(int i = 2; i <= Math.sqrt(n); i++){
                // 碰到能整除的因子
                if(n % i == 0){
                    // 不断地除这个因子直到不能整除为止，因子数加一，进入下一次循环
                    while(n % i == 0){
                        n = n / i;
                    }
                    ret++;
                }
            }
            // 当循环结束n不为1，即没能整除，说明此时的n也是一个因子
            if(n != 1) ret++;
            System.out.println(ret);
        }
    }
}

编辑于 2021-07-17 00:40:13 回复(0)

牛客306032403号

我来吐槽一下，牛客这为啥一提交就弹出一堆测试用例，也不说是哪个错的，这么多咋看呢

发表于 2021-05-22 13:37:05 回复(0)

思晓

#include <stdio.h>
 
int main()
{
    int n,num=0;
    while(scanf("%d",&n)!=EOF)
    {
        //int temp=n;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                num++;
                while(n%i==0)
                    n/=i;
            }
            if(n==1)
                break;
        }
        if(n!=1)
            num++;
        printf("%d\n",num);
        num=0; //初始化num不要忘了
    }
    return 0;
}

发表于 2020-04-16 13:46:59 回复(0)

hestyle

$\color{blue}解题思路：$
这道题和上一道题 PAT乙级(Basic Level)练习题分解因数是一样的，只不过上一题是让你输出分解的因数序列，此题是让你计算因子个数。
关于如何分解素数因子，请参考上一篇博客，有详细的解释，这里不再赘述。
我们只需将上一题稍微改造一下即可。

$\color{blue}代码实现：$

#include <iostream>
(720)#include <math.h>
using namespace std;

int main(int argc, const char * argv[]) {
    int number = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        //因子个数
        int count = 0;
        //只需要从[2, sqrt(number)]试探即可
        int maxEle = sqrt(number);
        for (int i = 2; i <= maxEle && number != 1; ++i) {
            //如果能分解出i，则一直分解出i，直到不能再分解，这样可以避免分解出i的倍数（i的倍数一定是合数）
            if (number % i == 0) {
                ++count;//因子个数自增
                while (number % i == 0) {
                    number /= i;
                }
            }
        }
        //如果最后number > 1,说明还有一个素数因子，比如当输入2、3时，并没有进入for循环
        printf("%d\n", number > 1 ? count + 1 : count);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104659060

发表于 2020-03-04 18:17:48 回复(0)

C/C++

不偷不抢安度因_

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int is_relative(int n)
{
    if(n == 2)
        return 1;//质数
    int s = sqrt(n);
    for(int j = 2; j <= s; j++)
    {
        if(n % j == 0)
            return j;//有因数j
    }
    return 1;
}
 
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int x;
        int temp = -1;
        int count = 0;
        while((x = is_relative(n)) != 1)
        {
            if(x != temp)
            {
                temp = x;
                count++;
            }
            n = n/x;
        }
        if(temp != n)    count++;
        printf("%d\n", count);
    }
}

编辑于 2020-03-03 12:19:56 回复(0)

小周好饿

// write your code here cpp
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int n=0;
    while(cin>>n)
    {
        int sum=0;
        for(int i=2;i<sqrt(n);i++)
        {
            if(n%i==0)
                sum++;//除则除尽
            while(n%i==0)
                n/=i;
        }
        //n最后大于1 则出现大于sqrt(n)的因子 
        if(n!=1)sum+=1;
        cout<<sum<<endl;
    }
    return 0;
}

发表于 2019-12-09 23:46:02 回复(0)

因子个数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题