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

erdf99

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

复制代码

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long LL;
   
5. LL x = 600851475143,ans;
   
6. 
   
7. int main()
   
8. {
   
9.     for(LL i=2;i<=x;i++)
   
10.         if(x%i==0)
    
11.         {
    
12.             ans = max(ans,i);
    
13.             while(x%i==0) x /= i;
    
14.         }
    
15.     if(x>1) ans = x;
    
16.     cout<<ans<<endl;
    
17.     return 0;
    
18. }

复制代码

叶落了

#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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main() {
   
5.     unsigned long long int n, i;
   
6.     n = 600851475143;
   
7. 
   
8.     for (i = 2; i <= n; i++) { // 将n从最小质数2逐个数判断是否为因子，是的话除去
   
9.         while (i != n) { // 当i与n相等时，也就是找到了n的最大质因子.(n一定是原数的因子；且n不可能既等于i，又不是质数，因为n已经除去了小于i的质因子)
   
10.             if (n % i == 0) { // 如果i是n的因子，则除去i
    
11.                 n /= i;
    
12.             } else { // 如果i不是n的因子，则判断下一个数
    
13.                 break;
    
14.             }
    
15.         }
    
16.     }
    
17.     // 输出最后的质因子
    
18.     cout << n << endl;
    
19. }

复制代码