文章

0

粉丝

1

获赞

5

访问

4359

头像
分解质因数
推荐阅读
P1885
发布于2022年6月9日 23:16
阅读数 692

我们直接从 2 开始除,除到他的 sqrt(n) 向下取整即可。这样除出来每一个能除尽的数一定都是质数。

由于每次我们都把遇到能取余的数和他的倍数都除尽了,所以下一个能除尽的一定也是质数(还是进行了筛法)。

同时他成对的约数(大于 sqrt(n) 向下取整 的那个)也提前出现了。 例如 90 第一次除 2 后得 45。 后面一直除只会逐渐变小,肯定会小于 sqrt(n) 向下取整。 所以除到这即可。

这样就只可能剩下一个大于他的因数。

不过题目给的数据这里如果数字本身是一个质数这里就直接不用输出了,似乎有点不合理。(或者需要说明下?)

#include <iostream>
using namespace std;
void calc(int n) {
    if (n == 1) return;
    int a = n;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            cout << i;
            n /= i;
            if (n != 1) cout << "*";
        }
    }
    if(n== a) return;
    if (n > 1) cout << n;
    cout << endl;
}
int main() {
    int n;
    while (cin >> n) {
        calc(n);
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发