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

yhhpf

永恒的蓝色梦想 发表于 2020-8-21 16:05
小学就讲过的啊……

小学讲过太多东西了，都忘了，哈哈。
回头再看回头再看~~~

yhhpf

永恒的蓝色梦想 发表于 2020-8-21 16:05
哦，这个版本没有优化，而且不是通用的。

是我想太多

1. a = 600851475143
   
2. l = []
   
3. while a != 1:
   
4.     for i in range(2, a + 1):
   
5.         if a % i == 0:
   
6.             l.append(i)
   
7.             a = a // i
   
8.             break
   
9. print(l)
   
10. print(max(l))

复制代码

前面还在算质数...我天...算半天...

永恒的蓝色梦想

KingFish-v- 发表于 2020-8-10 19:30
我看了老哥在85楼给出的python答案

这个是通用版：

1. def maxPrimeDivisor(num: int) -> int:
   
2.     if isinstance(num, int):
   
3.         if num < 2:
   
4.             raise ValueError("No prime divisor.")
   
5. 
   
6.         while not num & 1:
   
7.             num >>= 1
   
8. 
   
9.         if num == 1:
   
10.             return 2
    
11. 
    
12.         max = num ** 0.5
    
13.         divisor = 3
    
14. 
    
15.         while divisor <= max:
    
16.             if num % divisor:
    
17.                 divisor += 2
    
18.                
    
19.             else:
    
20.                 num //= divisor
    
21. 
    
22.                 while not num % divisor:
    
23.                     num //= divisor
    
24. 
    
25.                 if num == 1:
    
26.                     return divisor
    
27.                
    
28.                 max = num ** 0.5
    
29. 
    
30.         return num
    
31. 
    
32.     raise TypeError("Argument must be an integer.")

复制代码

a315734685

借鉴了 Mikel 的代码稍改了一点, 基本是秒出结果.

def prime(x):
    primes = []
    sum = 1
    for i in range(2, x//2):
        if x % i == 0:
            primes.append(i)
            sum *= i
            if sum == x:
                break
        # print(sum)
    return primes[-1]

print(prime(600851475143))

有马_冬巳

'''13195 的质数因子有 5, 7, 13 和 29。
600851475143 的最大质数因子是多少？'''
def sqrt(n):
    return int(n**(0.5))

def max_prime_factor(num):
    var = 0
    if num == 1:
        print(prime_factors)
        print(factor)

    elif num != 1:
        for factor in range(int(math.sqrt(num)), 0, -1):
            if num%factor == 0:
                check = 0
                for prime in range(2, int(math.sqrt(factor)+1)):
                    if factor%prime == 0:
                        check += 1
                        break
                    max_prime_factor = factor
                if check == 0 :
                    break
        print("%d 的最大质因子是: %d" %(num,factor))

start_max_prime_factor = time.time()
max_prime_factor(600851475143)
time_max_prime_factor = time.time() - start_max_prime_factor
print("%f秒" %time_max_prime_factor)


600851475143 的最大质因子是: 6857
0.073410秒

Process finished with exit code 0

gonorth

import math as m
def is_prime(num):
    if num > 1:
        if num == 2:
            return True
        if num % 2 == 0:
            return False
        for current in range(3, int(m.sqrt(num) + 1), 2):
            if num % current == 0:
                return False
        return True
    return False

def div(num):
    list1 = [0]
    for each in range(3, int (m.sqrt(num)), 2):
        if num % each == 0 :
            if is_prime(each):
                list1.pop()
                list1.append(each)
    print (list1)


div(600851475143)

xg-sco

1. # include <stdio.h>
   
2. # include <math.h>
   
3. 
   
4. int main ()
   
5. {
   
6.         long long int max = -1024;
   
7.         long long int num;
   
8.         printf("请输入一个数：");
   
9.         scanf("%lld", &num);
   
10.        
    
11.         for (int i = 2; i < sqrt(num); i++)
    
12.         {
    
13.                 if (num % i == 0)
    
14.                 {
    
15.                         printf("%d ", i);
    
16.                         if(i > max)
    
17.                         {
    
18.                                 max = i;
    
19.                         }
    
20.                 }
    
21.         }
    
22.         printf("\n");
    
23.         printf("max = %lld\n", max);
    
24.        
    
25.         return 0;
    
26. }

复制代码

a1351468657

翅膀团 发表于 2015-6-29 16:25
#include

int main(void)

int类型能存下600851475143吗？

酷爱语言的小白

1. def factor_max(n):
   
2.     i = n-1
   
3.     while i < n:
   
4.         i += -1
   
5.         if n% i == 0:
   
6.             return i
   
7. n = 600851475143
   
8. i = 1
   
9. list1 = []
   
10. while i <= n:
    
11.     if n% i == 0 and factor_max(i) == 1:
    
12.         list1.append(i)
    
13.         print(i)
    
14.         n = n/ i
    
15.     i += 1

复制代码

Kuri5u

1. target = 600851475143
   
2. i = 2
   
3. result = []
   
4. while i<=target:
   
5.     if target%i==0:
   
6.         while target%i==0:
   
7.             target=target//i
   
8.         result.append(i)
   
9.     i+=1
   
10. print(result)        
    
11.         
    

复制代码

from百度：
1没有质因子。
5只有1个质因子，5本身。（5是质数。）
6的质因子是2和3。(6 = 2 × 3)
2、4、8、16等只有1个质因子：2（2是质数，4 = 2，8 = 2，如此类推。）
10有2个质因子：2和5。(10 = 2 × 5)

中国好青年

a = []
c = []
for each in range(3,10000):
    for i in range(2,each):
        if each % i != 0:
            if i == each - 1:
                a.append(each)
        else:
            break
b = int(input(':'))
for i in a:
    if b % i == 0:
        c.append(i)
      
    else:
        continue
        
print(max(c))
这算法挺慢的，望大佬指点

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. //target = 600851475143
   
5. unsigned long long int target = 600851475143;
   
6. static int count;
   
7. 
   
8. int find_max_prime_factor(unsigned long long int n)
   
9. {
   
10.         int i;
    
11.        
    
12.         for(i=(int)sqrt((double)n);i>=2;i--)
    
13.         {
    
14.                 if (!(n%i)) return i;
    
15.                 count += 1;
    
16.         }
    
17.         return 0;
    
18. }
    
19. 
    
20. int main(void)
    
21. {
    
22.         printf("result is %d\n", find_max_prime_factor(target));
    
23.         printf("count = %d\n", count);
    
24.        
    
25.         return 0;
    
26. }

复制代码

鱼塘里的鱼儿

#include <iostream>
using namespace std;
int main()
{
        int sum=0;
        for(int i=2;i<600851475143;i++)
        {
                if(600851475143%i==0)
                {for(int i0=2,a=0;i0<i;i0++)
                        {
                        if(i%i0==0)
                                {
                                 break;
                                }
                         if(i0==i-1)
                                 {sum=i;
                                  cout<<sum<<endl;
                                 }
                        }
               
                }
        }
        cout<<sum;
}
我用c++写的
每一个我都输出了

ft215378

factors = []
x = 2
while x == 2:
    if num % x == 0:
        factors.append(x)
        num /= x
        continue
    else:
        break
x = 3
while x <= num:
    if num % x == 0:
        factors.append(x)
        num /= x
        continue
    else:
        x += 2

番杰

1. #include<stdio.h>
   
2. 
   
3. #define MAX 600851475143L
   
4. 
   
5. int main(void)
   
6. {
   
7.         int flag = 0,max ;
   
8.        
   
9.         for(int i = 2;i<(MAX/2);i++)
   
10.         {
    
11.                 flag = 0;
    
12.                 if(MAX % i == 0)
    
13.                 {
    
14.                         for(int j=2;j<(i/2);j++)
    
15.                         {
    
16.                                 if(i % j == 0)
    
17.                                 {
    
18.                                         flag = 1;
    
19.                                         break;
    
20.                                 }
    
21.                         }
    
22.                         if(flag == 0)
    
23.                         {
    
24.                                 max = i;
    
25.                         }
    
26.                 }                
    
27.         }
    
28. 
    
29.         printf("%d",max);
    
30.        
    
31.         return 0;
    
32. }

复制代码

learner-ray

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

int main(void)
{
        long long a = 600851475143;
        char ch;
        int i;
        int j;
        int max = 0;
       
        for (i = 3; i < sqrt(a); i++)
        {
                ch = 0;
                if (a % i == 0)
                {
                        for (j = 2; j < i; j++)
                        {
                                if (i % j == 0)
                                {
                                        ch = 1;
                                        break;
                                }
                        }
                        if (ch == 0)
                        {
                                max = i;
                        }
                }
        }
       
        printf("max = %lld\n", max);
        return 0;
}

guosl

这个题目大家都能解出，有的效率高，有的效率就有待提高。但差别不大。下面我想通过几种不同的编程来介绍一下平行编程。
首先本题解决的最原始的编程方法是C/C++。我的代码如下：

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. const long long N=600851475143LL;
   
6. const long long D=775146;
   
7. 
   
8. bool isprime(long long n)
   
9. {
   
10.   if((n&1)==0)
    
11.     return false;
    
12.   long long d=(long long)sqrt((double)n);
    
13.   for(long long i=3; i<=d; i+=2)
    
14.   {
    
15.     if(n%i==0)
    
16.       return false;
    
17.   }
    
18.   return true;
    
19. }
    
20. 
    
21. int main(void)
    
22. {
    
23.   long long M=0;
    
24.   for(long long i=1; i<=D; ++i)
    
25.   {
    
26.     if(N%i==0)
    
27.     {
    
28.       long long K=N/i;
    
29.       if(isprime(K))
    
30.         M=(K>M)?K:M;
    
31.       else if(isprime(i))
    
32.         M=(i>M)?i:M;
    
33.     }
    
34.   }
    
35.   cout<<M<<endl;
    
36.   return 0;
    
37. }
    
38. 
    

复制代码

这个程序在Ryzen5 3600的CPU的Unbuntu20.04系统上运行时间是：0.00867346秒，答案是：6857。

guosl

接下来我们用OpenMP方式来对本程序进行加速，由于本身的数据不是很大，所以可能会出现运行时间不会降低有时反而增加的情况，但随着现在电子工业的发展，CPU全面向多核心方向发展（现在手机的CPU都基本上是8核），所以平行编程的学习是非常有性价比学习。

1. #include <iostream>
   
2. #include <cmath>
   
3. #include <omp.h>
   
4. using namespace std;
   
5. 
   
6. const long long N=600851475143LL;
   
7. const long long D=775146;
   
8. 
   
9. inline bool isprime(long long n)
   
10. {
    
11.   if((n&1)==0)
    
12.     return false;
    
13.   long long d=(long long)sqrt((double)n);
    
14.   for(long long i=3; i<=d; i+=2)
    
15.   {
    
16.     if(n%i==0)
    
17.       return false;
    
18.   }
    
19.   return true;
    
20. }
    
21. 
    
22. int main(void)
    
23. {
    
24.   long long M=0;
    
25.   #pragma omp parallel for reduction(max:M)
    
26.   for(long long i=1; i<=D; ++i)
    
27.   {
    
28.     if(N%i==0)
    
29.     {
    
30.       long long K=N/i;
    
31.       if(isprime(K))
    
32.         M=(K>M)?K:M;
    
33.       else if(isprime(i))
    
34.         M=(i>M)?i:M;
    
35.     }
    
36.   }
    
37.   cout<<M<<endl;
    
38.   return 0;
    
39. }
    
40. 
    

复制代码

这个程序在Ryzen5 3600的CPU的Unbuntu20.04系统上运行时间是：0.00175184秒，答案是：6857。从代码可以看出代码改变得并不多，但加速比却达到了：4.95。

guosl

再接下来我们用GPU编程来加速这个程序，并通过这个例子来初步了解一下OpenACC，同样现在众核编程（通俗来讲就是在计算加速卡上进行计算的加速，显卡计算如：CUDA，OpenACC等）是国内大型计算机进行快速运算的一种主要手段所以会这样的计算将来就业的路子有多了一条。

1. #include <iostream>
   
2. #include <openacc.h>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. const long long N=600851475143LL;
   
7. const long long D=775146;
   
8. 
   
9. #pragma acc routine
   
10. bool isprime(long long n)
    
11. {
    
12.   if((n&1)==0)
    
13.     return false;
    
14.   long long d=(long long)sqrt((double)n);
    
15.   for(long long i=3; i<=d; i+=2)
    
16.   {
    
17.     if(n%i==0)
    
18.       return false;
    
19.   }
    
20.   return true;
    
21. }
    
22. 
    
23. int main(void)
    
24. {
    
25.   double t=omp_get_wtime();
    
26.   long long M=0;
    
27. #pragma acc kernels loop reduction(max:M)
    
28.   for(long long i=1; i<=D; ++i)
    
29.   {
    
30.     if(N%i==0)
    
31.     {
    
32.       long long K=N/i;
    
33.       if(isprime(K))
    
34.         M=(K>M)?K:M;
    
35.       else if(isprime(i))
    
36.         M=(i>M)?i:M;
    
37.     }
    
38.   }
    
39.   cout<<M<<t<<endl;
    
40.   return 0;
    
41. }
    
42. 
    

复制代码

上面两个程序都是用g++编译的，但本程序是用Nvidia公司的开放免费开发工具包HPC Toolkits中的nvc++编译的。
这个程序在GTX970的GPU的Unbuntu20.04系统上运行时间是：0.08391秒，答案是：6857。从代码可以看出代码改变得并不多，但加速比却<1。但这主要是两个原因造成的：
1. 这个问题的计算量本身并不大，但每个计算单元中的计算相对比较复杂。
2. 显卡计算特别适合计算量特别大，但本身的计算问题非常简单的问题，如矩阵的加与乘。

guosl

再接下来我们用GPU的CUDA编程来实现这个程序，并通过这个例子来初步了解一下CUDA与OpenACC的不同。对于编写OpenACC程序其实只要写好原始的C++程序，然后通过加入编译的导语来实现GPU的代码实现，优点是是比较容易编程，缺点是对于逻辑复杂的程序用OpenACC总是有点放不开手脚，因为里面的GPU代码是由编译器来实现的，你根本就不知道具体的代码是啥，有时候人工智能就是某种“人工智障”，所以效率可能不高。这个时候用CUDA来写就会有一种正好挠到痒处的感觉。
下面的代码是按Nvidia公司的CUDA规范写的，在GTX970的GPU的Unbuntu20.04系统上编译运行的。

1. #include "cuda_runtime.h"
   
2. #include "device_launch_parameters.h"
   
3. #include <stdio.h>
   
4. 
   
5. const long long N = 600851475143LL;
   
6. const long long D = 775146LL;
   
7. const int nBlockDim = 128;
   
8. const int nBlocks = 128;
   
9. 
   
10. __device__ bool isprime(long long n)
    
11. {
    
12.   if ((n & 1) == 0)
    
13.     return false;
    
14.   long long d = (long long)sqrt((double)n);
    
15.   for (long long i = 3; i <= d; i += 2)
    
16.   {
    
17.     if (n % i == 0)
    
18.       return false;
    
19.   }
    
20.   return true;
    
21. }
    
22. 
    
23. __global__ void findprime(long long s, long long* r)
    
24. {
    
25.   __shared__ long long lm[nBlocks];
    
26.   long long M = 0;
    
27.   int n = s + threadIdx.x + blockIdx.x * nBlockDim;
    
28.   if (n <= D)
    
29.   {
    
30. 
    
31.     if (N % n == 0)
    
32.     {
    
33.       long long K = N / n;
    
34.       if (isprime(K))
    
35.         M = (K > M) ? K : M;
    
36.       else if (isprime(n))
    
37.         M = (n > M) ? n : M;
    
38.     }
    
39.   }
    
40.   lm[threadIdx.x] = M;
    
41.   __syncthreads();
    
42.   n = nBlockDim / 2;
    
43.   while (n > 0)
    
44.   {
    
45.     if (threadIdx.x < n)
    
46.     {
    
47.       if (lm[threadIdx.x] < lm[threadIdx.x + n])
    
48.         lm[threadIdx.x] = lm[threadIdx.x + n];
    
49.     }
    
50.     n /= 2;
    
51.     __syncthreads();
    
52.   }
    
53.   if (threadIdx.x == 0)
    
54.     r[blockIdx.x] = lm[0];
    
55. }
    
56. 
    
57. int main(void)
    
58. {
    
59.   long long* pM = NULL;
    
60.   long long* p_dM = NULL;
    
61.   long long s = 2, nMaxPrime = 2;
    
62.   cudaError_t cudaStatus;
    
63.   int nPId = 0;
    
64.   cudaStatus = cudaSetDevice(nPId);//设置计算卡
    
65.   if (cudaStatus != cudaSuccess)
    
66.   {
    
67.     fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
    
68.     goto Error;
    
69.   }
    
70.   cudaDeviceProp deviceProp;
    
71.   cudaStatus = cudaGetDeviceProperties(&deviceProp, nPId);
    
72.   if (cudaStatus != cudaSuccess)
    
73.     goto Error;
    
74.   printf("GPU Device %d: "%s" with compute capability %d.%d\n\n", nPId, deviceProp.name, deviceProp.major, deviceProp.minor);
    
75.   cudaStatus = cudaSetDevice(0);
    
76.    //在主机上分配锁定内存
    
77.   cudaStatus = cudaHostAlloc((void**)&pM, nBlocks * sizeof(long long), cudaHostAllocDefault);
    
78.   if (cudaStatus != cudaSuccess)
    
79.   {
    
80.     fprintf(stderr, "CUDA alloc memory failed!");
    
81.     goto Error;
    
82.   }
    
83. //在显卡上分配内存
    
84.   cudaStatus = cudaMalloc((void**)&p_dM, nBlocks * sizeof(long long));
    
85.   if (cudaStatus != cudaSuccess)
    
86.   {
    
87.     fprintf(stderr, "cudaMalloc failed!");
    
88.     goto Error;
    
89.   }
    
90.   while (s <= D)
    
91.   {
    
92.     findprime << <nBlocks, nBlockDim >> > (s, p_dM);//进行显卡计算
    
93.     cudaStatus = cudaGetLastError();
    
94.     if (cudaStatus != cudaSuccess)
    
95.     {
    
96.       fprintf(stderr, "addKernel launch failed: %s\n", cudaGetErrorString(cudaStatus));
    
97.       goto Error;
    
98.     }
    
99.     cudaStatus = cudaDeviceSynchronize();//等待显卡的计算完成
    
100.     if (cudaStatus != cudaSuccess)
     
101.     {
     
102.       fprintf(stderr, "cudaDeviceSynchronize returned error code %d after launching addKernel!\n", cudaStatus);
     
103.       goto Error;
     
104.     }
     
105.     cudaStatus = cudaMemcpy(pM, p_dM, nBlocks * sizeof(long long), cudaMemcpyDeviceToHost);//从显卡取回计算的结果
     
106.     if (cudaStatus != cudaSuccess)
     
107.     {
     
108.       fprintf(stderr, "cudaMemcpy failed!");
     
109.       goto Error;
     
110.     }
     
111.     for (int i = 0; i < nBlocks; ++i) //归并结果
     
112.       nMaxPrime = (nMaxPrime > pM[i]) ? nMaxPrime : pM[i];
     
113.     s += nBlocks * nBlockDim;
     
114.   }
     
115.   printf("%lld\n", nMaxPrime);
     
116. Error:
     
117.   if (p_dM != NULL)
     
118.   {
     
119.     cudaFree(p_dM);
     
120.     p_dM = NULL;
     
121.   }
     
122.   if (pM != NULL)
     
123.   {
     
124.     cudaFreeHost(pM);
     
125.     pM = NULL;
     
126.   }
     
127.   return 0;
     
128. }
     

复制代码

运行时间是：0.001818秒，答案是：6857。在这里看来人工智能还是比不过了人工。