V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
windbadboy
V2EX  ›  编程

分解质因数的程序,麻烦大家帮忙优化下。

  •  
  •   windbadboy · 2023-03-16 09:48:02 +08:00 · 1444 次点击
    这是一个创建于 600 天前的主题,其中的信息可能已经有所发展或是发生改变。

    #include <iostream>

    using namespace std;

    void fjzys(int n);

    int main() { int n; cout << "输入一个数:"; cin >> n; cout << "质因数为:"; fjzys(n); }

    void fjzys(int x) { //2,3,5,7 是质数 if(x == 2 || x == 3 || x == 5 || x ==7) cout << x << " "; else {

        if(x % 2 == 0)
        {
                fjzys(x / 2);
                cout << 2 << " ";
        }
        else if(x % 3 == 0)
        {
                fjzys(x / 3);
                cout << 3 << " ";
        }
        else if(x % 5 == 0)
        {
                fjzys(x / 5);
                cout << 5 << " ";
        }
        else if(x % 7 == 0)
        {
                fjzys(x / 7);
                cout << 7 << " ";
        }
        else
        		//如果无法被 2,3,5,7 整除,则直接判断为质数
                cout << x << " ";
    
        }
    

    }

    业务学习编程,始终感觉程序写得有点重复,算法不理想。

    9 条回复    2023-03-18 17:22:25 +08:00
    tlxxzj
        1
    tlxxzj  
       2023-03-16 10:17:08 +08:00
    #include <iostream>

    void fjzys(int n) {
    if(n < 2) {
    return;
    }
    bool is_prime = true;
    int x = n;
    int m = n / 2;
    for(int i = 2; i < m; i++) {
    while(x % i == 0) {
    is_prime = false;
    std::cout<<i<<" ";
    x = x / i;
    }
    }
    if(is_prime) {
    std::cout<<n;
    }
    }


    int main()
    {
    fjzys(123456);
    return 0;
    }
    lapulasi
        2
    lapulasi  
       2023-03-16 10:17:21 +08:00
    Donald E.Knuth The Art of Computer Programming (vol.2) 4.5.4 Factoring into Primes
    tlxxzj
        3
    tlxxzj  
       2023-03-16 10:17:28 +08:00
    太久没写 c++了
    chenluo0429
        4
    chenluo0429  
       2023-03-16 11:46:17 +08:00 via Android
    143 表示有点难过
    opengps
        5
    opengps  
       2023-03-16 11:49:44 +08:00
    //如果无法被 2,3,5,7 整除,则直接判断为质数
    这个逻辑过于简单粗暴啊 ,正常不应该是穷举判断吗,输入 N ,遍历逐个判断除以 2,2 ,3 ,4 ,5 。。。。N-1
    1234rty
        6
    1234rty  
       2023-03-16 12:00:06 +08:00 via Android
    这是在搞笑吗,初中数学老师应该没教给你质数是无法被 2,3,5,7 整除的整数吧?
    princelai
        7
    princelai  
       2023-03-16 12:54:16 +08:00
    我虽然不会写 C,但可以让 chatgpt 帮你写一个你作为参考

    loopinfor
        8
    loopinfor  
       2023-03-16 13:30:12 +08:00 via Android
    理论上需要穷举 2 到 N 开平方的所有数
    opengps
        9
    opengps  
       2023-03-18 17:22:25 +08:00
    昨天随手写了个穷尽质数的代码,单线程现在跑了 4 个小时,495 万数据里找到了 34.5 万个质数了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1426 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:47 · PVG 07:47 · LAX 15:47 · JFK 18:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.