首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数：1234010 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的整数 n，从小到大依次输出它的全部质因子。即找到这样的质数 p_1, p_2, \cdots, p_k，使得 n = p_1 \times p_2 \times \cdots \times p_k。

输入描述:
\hspace{15pt}在一行上输入一个整数 n \left( 2 \leqq n \leqq 2 \times 10^9 + 14 \right) 代表待分解的整数。


输出描述:
\hspace{15pt}在一行上从小到大输出若干个整数，代表 n 的质因子。
示例1

输入

180

输出

2 2 3 3 5

说明

\hspace{15pt}在这个样例中，180 = 2 \times 2 \times 3 \times 3 \times 5。
示例2

输入

47

输出

47
算法知识视频讲解
添加回答
C
牛客635475573号头像 牛客635475573号

#include <stdio.h>

int main() {
    int n,temp;
    scanf("%d",&n);
    while (n%2==0) {//处理偶数因子
        printf("2 ");
        n=n/2;
    }
…    //处理剩余情况
    if(n>1){
        printf("%d ",n);
    }

    return 0;
}
发表于 2025-07-24 20:20:40 回复(0)
C
服了你个老六的靓仔很年轻头像 服了你个老六的靓仔很年轻
#include <math.h>
#include <stdio.h>
#include<string.h>
void find( int x) {
    for (int i = 2; i <x+1; i++) {
        int t = x % i, num = 0;
        if (i<sqrt(x)||i==sqrt(x)) {
            if (t == 0) {
                printf("%d ", i);
                num = x / i;
                find(num);
                break;
            }
           
        } else {
            printf("%d ", x);
            break;
        }

    }
}
int main() {
     int x;
    scanf("%d", &x);
    find(x);
}
发表于 2025-06-18 15:22:16 回复(0)
C
jadezzy头像 jadezzy 
#include <math.h>
#include <stdio.h>

int main() {
    int n;
    int prime=2;
    scanf("%d",&n);
    while(prime<=sqrt(n)){
        while(n%prime!=0){
            prime++;
            if(prime>sqrt(n)){
                printf("%d ",n);
                return 0;
            }
        }
        n=n/prime;
        printf("%d ",prime);
        
    }
    if(prime>sqrt(n)){
                printf("%d ",n);
                return 0;
            }

    return 0;
}

发表于 2025-04-03 00:13:51 回复(0)
C
菜的没话说头像 菜的没话说 
#include <stdio.h>
int main() {
    unsigned int a;
    while (scanf("%d", &a) != EOF) {
        for (unsigned int i = 2; i * i <= a; i++) {
            while (a % i == 0) {
                printf("%d ", i);
                a = a / i;
            }
        }
        if (a != 1) {
            printf("%d\n", a);
        }
    }
    return 0;
}

发表于 2024-09-11 17:09:22 回复(0)
C
牛客653305411号头像 牛客653305411号 
#include <math.h>
#include <stdio.h>

int main() {
    int num;
    /* prime 初始值为2 */
    int prime = 2; 
    /* 输入值 */
    scanf("%d", &num);

    while (prime <= sqrt(num)) {
        /* prime试探法，如果num不能整除，就代表prime不为因数 */
        if ( 0 != (num % prime)) {
            prime++;
        }
        /* 如果num不能整除，就代表prime为因数 */
        /* 1、打印因数 */
        /* 2、更新num的值 */
        else {
            printf("%d ", prime);
            num /= prime;
            prime = 2;
        }
        /* 如果prime已经大于sqrt(num)，就代表num本身为一个超大的质数，直接输出 */
        if (prime > sqrt(num)) {
            printf("%d ", num);
        }
    }

}
发表于 2024-08-24 16:12:25 回复(0)
C
唐凌Zero头像 唐凌Zero
最快的取质数的办法就是提前计算出质数表放进全局变量里。这里0到1000的质数已经可以通过全部测试用例，但严谨点的话应该生成到2的15次方以内的质数。 
#include <stdio.h>

// 提前算出取0到1000的质数。
const int prime_list[168]={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};

int main() {
    int a;
    while (scanf("%d",&a) != EOF)
    {
        int x=0;
        while(a>1)
        {
            int found=0;
            for(int i=x;i<168;i++)
            {
                const int pn=prime_list[i];
                if((a%pn)==0)
                {
                    a/=prime_list[i];
                    printf("%d ",prime_list[i]);
                    x=i;
                    found=1;
                    break;
                }
            }
            if(!found)
            {
                printf("%d ",a);
                break;
            }
        }
    }
    return 0;
}


发表于 2024-08-17 06:15:26 回复(0)
C
莱顿普西斯头像 莱顿普西斯
#include <math.h>
#include <stdio.h>

int main(int argc, char const *argv[])
{
    int num;
    scanf("%d", &num);
    for (int i = 2; i < sqrt(num) + 1; ++i) {
        if (num % i == 0) {
            printf("%d ", i);
            num = num / i;
            i = 1;          
        }      
    }
    printf("%d", num);
    return 0;
}
发表于 2024-08-10 13:10:21 回复(0)
C
小牛zzb头像 小牛zzb
(1)质因子要小于这个数开根号，很关键 
#include <math.h>
#include <stdio.h>

int main() {
    int input = 0;

    scanf("%d",&input);

    int temp1 = 2, temp2 = input;
    while(temp2 !=1)
    {
        if(temp1 > sqrt(temp2))
            temp1 = temp2;
        if(temp2%temp1 == 0)
        {
            printf("%d ",temp1);
            temp2 = temp2/temp1;
        }
        else 
        {
            temp1++;
        }
    }
    return 0;
}


编辑于 2024-04-15 19:11:19 回复(0)
C
垂耳兔在泡澡_头像 垂耳兔在泡澡_ 
#include <math.h>
#include <stdio.h>

int main() {
    int a,i;
    scanf("%d",&a);

    for(i=2;i<=sqrt(a);i++)
    {
        if(a%i==0)
        {
            printf("%d ",i);
            a=a/i;
            i--;
        }
    }
    printf("%d\n",a);
    return 0;
}

编辑于 2024-02-14 12:16:18 回复(1)
C
啥子都不会捏头像 啥子都不会捏
最难的地方在于相同快速的判断质数，我怎么就想不到跟数的平方去比 
#include <stdio.h>
#include <stdbool.h>

int InputNum = 0;

bool IsPrime(int Num)
{
    bool ret  = true;
    if(2 == Num)
        return ret;
    if(0 == (Num %2))
        return false;
    for(int i = 2;i < Num && (i * i <=Num);i++)
    {
        if(0 == (Num % i))
        {
            ret = false;
            break;
        }
    }
    return ret;
}

int FindOnePrimeNum(int m)
{
    if(IsPrime(m))
    {
        printf("%d",m);
        return -1;
    }
    else{
    for(int i = 2;i <= m;i++)
    {
        if(!IsPrime(i))
            continue;
        if(0 == (m % i))
        {
            printf("%d ",i);
            return FindOnePrimeNum(m/i);
        }

    }
    }
    return  -1;
}

int main() {
    scanf("%d",&InputNum);
    FindOnePrimeNum(InputNum);
}


发表于 2024-01-05 15:57:47 回复(1)
C
猪猪侠的飞天梦头像 猪猪侠的飞天梦 
#include <stdio.h>
# include<math.h>
int main() {
    long long a, i = 1;
    scanf("%d",&a);
    if(a<4){
        printf("%d",a);
        return 0;
    }
    int k = sqrt(a);
    for (i = 2; i<=k; i++) {
        if (a%i==0) {
            printf("%d ",i);
            a = a/i;
            i = 1;
            k = sqrt(a);
        }
    
    }
    printf("%d ",a);
    return 0;
}

发表于 2023-12-01 19:19:25 回复(0)
C
想被叫靓仔的孤勇者最喜欢秋天头像 想被叫靓仔的孤勇者最喜欢秋天
#include <stdio.h>
int main() {
    int a,i=3;
    scanf("%d", &a);
    while(!(a&1)){printf("2 ");a=a>>1;}
    while(i*i<=a) {
        if(a%i==0){a/=i;printf("%d ",i);}
        else i+=2;
    }if(a!=1){printf("%d",a);}
    return 0;
}
运行时间3ms
占用内存352KB
#include <stdio.h>
int main() {
    int a,i=3,j=3,compare=9;
    scanf("%d", &a);
    while(!(a&1)){printf("2 ");a=a>>1;}
    while(compare<a) {
        if(a%i==0){a/=i;printf("%d ",i);}
        else i+=2;
        compare=(j=i);
        while (j>>=1) {
        compare<<=1;
        }
    }if(a!=1){printf("%d",a);}
    return 0;
}
运行时间3ms
占用内存320KB
结论是编译器底层算法已经基本优化到头了，上个世代的性能提升小技巧已经用不上了（
发表于 2023-09-24 18:49:03 回复(0)
C
牛客476102116号头像 牛客476102116号
//质数因子
//所求自然数除以大于1的最小之质数必须可除尽；
//得出的结果重复第一步；
//直到结果等于1时候所有除数集合
#include <stdio.h>
int main() {
    long int n;
    int i;
    while (scanf("%ld", &n)) {
        for (int i = 2; i * i <= n;) //i平方小于等于n表示除到算数平方根之前质数就取完了
        {
            if (n % i == 0) //取余为0就表示除以i这个质数可除尽，所以i为n的质数因子
            {
            printf("%d ", i);
            n = n / i; //这时候n该等于n除以i这个质数因子的结果了，然后循环寻找下一个质数因子
            } else i++;
        }
        break;
    }
    printf("%ld", n); //i的平方大与n，到了最后n本身就是质数
    return 0;
}
发表于 2023-07-20 22:46:40 回复(0)
C
牛客138923047号头像 牛客138923047号 
//难点在于减少循环次数，循环到输入的平方根结束，这样可以减少循环次数

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

int deter(int num)
{
    if(num == 1)
    {
        return 0;
    }
    int j;
    for(j = 2; j <= sqrt(num); j++)
    {
        if(num % j == 0)
        {
            return 0;
        }
        
    }
    return 1;
}

int main() {
    int num;
    int i;
    int temp;
    scanf("%d", &num);
    temp = num;
    for(i = 2; i <= sqrt(num); )
    {
        if(temp % i == 0 && deter(i))
        {
            printf("%d ", i);
            temp = temp / i;
        }
        else
        {
            i++;
        }
    }
    if(deter(num))
    {
        printf("%d ", num);
    }
    else if(deter(temp))
    {
        printf("%d ", temp);
    }
    return 0;
}

发表于 2023-06-26 18:21:55 回复(0)
提交观点

问题信息

排序
来自：2016乐视暑期实习生...
难度：
67条回答 126972浏览

热门推荐

通过挑战的用户

查看代码

相关试题

质数因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号