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

mathtimes

1. #include <cstdio>
   
2. #include <cmath>
   
3. #include <vector>
   
4. using std::vector;
   
5. int main()
   
6. {
   
7.     vector<long long> factor;
   
8.     long long num = 600851475143;
   
9.     int i = 2;
   
10.     while(1)
    
11.     {
    
12.         for(i=2;i<sqrt(num)+1;i++)
    
13.         {
    
14.             if(num%i==0)
    
15.             {
    
16.                 factor.push_back(i);
    
17.                 num /= i;
    
18.                 goto continuetodo;
    
19.             }
    
20.         }
    
21.         factor.push_back(num);
    
22.         break;
    
23.         continuetodo:;
    
24.     }
    
25.     long long max = 0;
    
26.     vector<long long>::iterator it;
    
27.     for(it=factor.begin();it!=factor.end();it++)
    
28.         if(*it>max)
    
29.             max = *it;
    
30.     printf("%d",max);
    
31. }

复制代码

jerryxjr1220

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "math"
   
6.         "time"
   
7. )
   
8. 
   
9. //题目3：
   
10. //
    
11. //13195 的质数因子有 5, 7, 13 和 29。
    
12. //
    
13. //600851475143 的最大质数因子是多少？
    
14. func main() {
    
15.         t := time.Now()
    
16.         limit := int64(math.Sqrt(600851475143))
    
17.         var remain int64 = 600851475143
    
18.         var max int64 = 2
    
19.         var i int64
    
20.         fmt.Println("分解质因数：")
    
21.         for i = 2; i < limit; i++ {
    
22.                 if remain%i == 0 {
    
23.                         remain /= i
    
24.                         fmt.Println(i)
    
25.                         if i > max {
    
26.                                 max = i
    
27.                         }
    
28.                         i = 2
    
29.                 }
    
30.         }
    
31.         if remain > max {
    
32.                 max = remain
    
33.         }
    
34.         fmt.Println("最大质因数是： ", max)
    
35.         tt := time.Now()
    
36.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
37. }
    

复制代码

输出：

1. GOROOT=C:\Program Files\Go #gosetup
   
2. GOPATH=C:\Users\Administrator\go #gosetup
   
3. "C:\Program Files\Go\bin\go.exe" build -o C:\Users\Administrator\AppData\Local\Temp\GoLand\___2go_build_GoProject_src.exe C:\Users\Administrator\Documents\GoProject\src\Euler03.go #gosetup
   
4. C:\Users\Administrator\AppData\Local\Temp\GoLand\___2go_build_GoProject_src.exe
   
5. 分解质因数：
   
6. 71                  
   
7. 839                  
   
8. 1471                 
   
9. 6857                 
   
10. 最大质因数是：  6857
    
11. 耗时： 2 ms         
    
12. 
    
13. 进程 已完成，退出代码为 0
    

复制代码

Go语言果然运行速度比Python快非常多

B1tetheDust

1. import math
   
2. import time
   
3. 
   
4. 
   
5. class FindPrimeFactor:
   
6. 
   
7.     def __init__(self, num):
   
8.         self.num = self.max_prime = num
   
9.         self.find_factor()
   
10.         print(self.max_prime)
    
11. 
    
12.     @staticmethod
    
13.     def find_prime(a_num):
    
14.         is_prime = 1
    
15.         for i in range(2, int(math.sqrt(a_num) + 1)):
    
16.             if a_num % i == 0:
    
17.                 is_prime = 0
    
18.         return is_prime
    
19. 
    
20.     def find_factor(self):
    
21.         divisor = int(math.sqrt(self.num))
    
22.         while (divisor - 1):
    
23.             if self.num % divisor == 0:
    
24.                 if self.find_prime(divisor):
    
25.                     self.max_prime = divisor
    
26.                     break
    
27.             divisor -= 1
    
28. 
    
29. 
    
30. start = time.perf_counter()
    
31. test = FindPrimeFactor(600851475143)
    
32. end = time.perf_counter()
    
33. print((end - start))

复制代码

清风揽月shine

import math


def prime_calc(num):
    """计算这个数字是否是质数
    质数：除了1和本身因数以外无其他
    """
    for x in range(2, int(math.sqrt(num) + 1)):
        if num % x == 0:
            return -1

    return num


def max_prime(num):
    """
    : 这里面最大的收获是一个数的质因数 肯定是在更号区间前一个 和更号区间后一个
    ：如此即可将数据范围缩小一个幂次方  加速计算效率
    :param num:
    :return:
    """
    prime_list = []
    for x in range(2, int(math.sqrt(num))):
        if num % x == 0 and prime_calc(x) != -1:
            prime_list.append(x)
    print(prime_list)
    print('最大质数因子:', max(prime_list))


if __name__ == '__main__':
    max_prime(600851475143)

开飞机的羊驼

num = 13195
list = []
list1 = []
#先用for循环寻找所有的因子并存储list
for i in range(1, num):
    if num % i == 0:
        list.append(i)
print(list)
# 用两个for循环来判断list中的因子那些是质数
for j in list:
    if (j != 1) and (j != num):
        for k in range(2, j):
            if j % k == 0 :
                break
        else:
            list1.append(j)
print(list1)
print("最大质数因子为%d"%list1[-1])

Asss-whom

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. const N: i64 = 600851475143;
   
5. 
   
6. fn main() {
   
7.     let now = Instant::now();
   
8.     let primes = make_prime();
   
9.     let num = primes
   
10.     .into_par_iter()
    
11.     .filter(|x| N % x == 0)
    
12.     .max()
    
13.     .unwrap();
    
14.     println!("{}", num);
    
15.     println!("耗时{}秒。", now.elapsed().as_secs_f32())
    
16. }
    
17. 
    
18. fn make_prime() -> Vec<i64> {
    
19.     let mut primes = Vec::new();
    
20.     let mut cur = 10;
    
21.     // bootstrap
    
22.     for i in 2..cur {
    
23.         if primes.iter().all(|p| i % p != 0) {
    
24.             primes.push(i);
    
25.         }
    
26.     }
    
27.     let n = (N as f64).sqrt() as i64 + 1;
    
28.     while cur < n {
    
29.         let next = std::cmp::min(cur * cur, n);
    
30.         let mut addition: Vec<_> = (cur..next)
    
31.             .into_par_iter()
    
32.             .filter(|x| {
    
33.                 for p in primes.iter() {
    
34.                     if x % p == 0 {
    
35.                         return false;
    
36.                     }
    
37.                     if x / p < *p {
    
38.                         break;
    
39.                     }
    
40.                 }
    
41.                 true
    
42.             })
    
43.             .collect();
    
44.         primes.append(&mut addition);
    
45.         cur = next;
    
46.     }
    
47.     primes
    
48. }

复制代码

6857
耗时0.008448秒。

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. }

复制代码