题目3：找出一个合数的最大质数因子

erdf99

long long factor(long long n) {//找出一个合数的最大质数因子 
        if (n == 2)return 2;
        if (n % 2 == 0) return factor(n / 2);
        for (int i = 3; i <= (sqrt(n)); i=i+2) {
                if (n % i == 0) return factor(n / i);
        }
        return n;
}

factor(600851475143) 结果6857

_乏趣味

for i in range(2,int(x**0.5)+1):
        if x%i==0:
                for m in range(2,i):
                        if i%m==0:
                                break
                        if m==i-1:
                                print(i)
                                max=i
                for k in range(2,int(pow(x/i,0.5))+1):
                        if i%k==0:
                                break
                        if k==int(pow(x/i,0.5)):
                                print(i)
                                max=i

Eca

#include <stdio.h>

int main() {
        long long int n;
        scanf("%lld", &n);
        printf("%lld=1", n);
        for (int i = 2; i <= n + 1; i++) {
                if (n % i == 0) {
                        printf("*%lld", i);
                        n /= i;
                }
        }

        return 0;
}

Kazimierz

1ms

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL x = 600851475143,ans;

int main()
{
    for(LL i=2;i<=x;i++)
        if(x%i==0)
        {
            ans = max(ans,i);
            while(x%i==0) x /= i;
        }
    if(x>1) ans = x;
    cout<<ans<<endl;
    return 0;
}

叶落了

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

int Determine(int i);
int Determine(int i)
{
        int n;
        if(i==1)
        {
                return 0;
        }
        if(i==2)
        {
                return i;
        }
        else if(i%2==0)
        {
                return 0;
        }
        else
        {
                for(n=2;n<=pow(i,0.5);n++)
                {
                        if(i%n==0)
                        {
                                return 0;
                        }
                }
                return i;
        }
}

int main(void)
{
        int i,k;
        unsigned long long int sum=1;
       
        for(i=1;i<=20;i++)
        {
                k=Determine(i);
                if(k)
                {
                        for(k;k*k<=20;k=k*k)
                        {
                                ;
                        }
                        printf("%d\n",k);
                        sum=sum*k;
                }
        }
        printf("最小的能被 1-20 中每个数整除的正整数是%lld\n",sum);
        return 0;
}

//思路
/*
2->2
3->3
2->4
5->5

7->7
2->8
3->9

11->11

13->13


2->16
17->17

19->19

利用一个定理，任何一个合数都可以拆成 质数积 形式，用集合(且可以多同一元素)取并集

还可以质数的次方判断
但必须引入一个纯合数的概念，质数积 形式=全部为同一个质数。
在它的前面，不可能有比它还需要（在数量上）这同一个质数的数了
*/

叶落了

叶落了 发表于 2023-6-18 09:50
#include
#include

应该算是最简单的了，笔算可以出

Ian_Li

C++练习 day3

#include <iostream>
using namespace std;

int main() {
    unsigned long long int n, i;
    n = 600851475143;

    for (i = 2; i <= n; i++) { // 将n从最小质数2逐个数判断是否为因子，是的话除去
        while (i != n) { // 当i与n相等时，也就是找到了n的最大质因子.(n一定是原数的因子；且n不可能既等于i，又不是质数，因为n已经除去了小于i的质因子)
            if (n % i == 0) { // 如果i是n的因子，则除去i
                n /= i;
            } else { // 如果i不是n的因子，则判断下一个数
                break;
            }
        }
    }
    // 输出最后的质因子
    cout << n << endl;
}