鱼C论坛

 找回密码
 立即注册
楼主: 欧拉计划

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

  [复制链接]
发表于 2020-8-21 16:36:56 | 显示全部楼层

小学讲过太多东西了,都忘了,哈哈。
回头再看回头再看~~~
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 17:35:24 | 显示全部楼层
永恒的蓝色梦想 发表于 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))
复制代码

前面还在算质数...我天...算半天...
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 19:20:36 | 显示全部楼层
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.         while not num & 1:
  6.             num >>= 1

  7.         if num == 1:
  8.             return 2

  9.         max = num ** 0.5
  10.         divisor = 3

  11.         while divisor <= max:
  12.             if num % divisor:
  13.                 divisor += 2
  14.                
  15.             else:
  16.                 num //= divisor

  17.                 while not num % divisor:
  18.                     num //= divisor

  19.                 if num == 1:
  20.                     return divisor
  21.                
  22.                 max = num ** 0.5

  23.         return num

  24.     raise TypeError("Argument must be an integer.")
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-9-1 16:38:19 | 显示全部楼层
借鉴了 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))
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-2 11:27:37 | 显示全部楼层
'''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
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-11-4 21:35:18 | 显示全部楼层
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)
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-12-26 09:51:20 | 显示全部楼层
  1. # include <stdio.h>
  2. # include <math.h>

  3. int main ()
  4. {
  5.         long long int max = -1024;
  6.         long long int num;
  7.         printf("请输入一个数:");
  8.         scanf("%lld", &num);
  9.        
  10.         for (int i = 2; i < sqrt(num); i++)
  11.         {
  12.                 if (num % i == 0)
  13.                 {
  14.                         printf("%d ", i);
  15.                         if(i > max)
  16.                         {
  17.                                 max = i;
  18.                         }
  19.                 }
  20.         }
  21.         printf("\n");
  22.         printf("max = %lld\n", max);
  23.        
  24.         return 0;
  25. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-3-6 10:49:34 | 显示全部楼层
翅膀团 发表于 2015-6-29 16:25
#include

int main(void)

int类型能存下600851475143吗?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-4-26 09:16:10 | 显示全部楼层
  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
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-5-3 17:41:08 | 显示全部楼层
  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)
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-5-16 21:39:34 | 显示全部楼层
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))
这算法挺慢的,望大佬指点
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-8-7 00:07:34 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <math.h>

  3. //target = 600851475143
  4. unsigned long long int target = 600851475143;
  5. static int count;

  6. int find_max_prime_factor(unsigned long long int n)
  7. {
  8.         int i;
  9.        
  10.         for(i=(int)sqrt((double)n);i>=2;i--)
  11.         {
  12.                 if (!(n%i)) return i;
  13.                 count += 1;
  14.         }
  15.         return 0;
  16. }

  17. int main(void)
  18. {
  19.         printf("result is %d\n", find_max_prime_factor(target));
  20.         printf("count = %d\n", count);
  21.        
  22.         return 0;
  23. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-2 16:12:01 | 显示全部楼层
#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++写的
每一个我都输出了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-8 13:24:33 | 显示全部楼层
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
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-25 16:55:02 | 显示全部楼层
  1. #include<stdio.h>

  2. #define MAX 600851475143L

  3. int main(void)
  4. {
  5.         int flag = 0,max ;
  6.        
  7.         for(int i = 2;i<(MAX/2);i++)
  8.         {
  9.                 flag = 0;
  10.                 if(MAX % i == 0)
  11.                 {
  12.                         for(int j=2;j<(i/2);j++)
  13.                         {
  14.                                 if(i % j == 0)
  15.                                 {
  16.                                         flag = 1;
  17.                                         break;
  18.                                 }
  19.                         }
  20.                         if(flag == 0)
  21.                         {
  22.                                 max = i;
  23.                         }
  24.                 }                
  25.         }

  26.         printf("%d",max);
  27.        
  28.         return 0;
  29. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-11-12 05:42:44 | 显示全部楼层
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;
}
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-12-30 20:16:19 | 显示全部楼层
这个题目大家都能解出,有的效率高,有的效率就有待提高。但差别不大。下面我想通过几种不同的编程来介绍一下平行编程。
首先本题解决的最原始的编程方法是C/C++。我的代码如下:
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;

  4. const long long N=600851475143LL;
  5. const long long D=775146;

  6. bool isprime(long long n)
  7. {
  8.   if((n&1)==0)
  9.     return false;
  10.   long long d=(long long)sqrt((double)n);
  11.   for(long long i=3; i<=d; i+=2)
  12.   {
  13.     if(n%i==0)
  14.       return false;
  15.   }
  16.   return true;
  17. }

  18. int main(void)
  19. {
  20.   long long M=0;
  21.   for(long long i=1; i<=D; ++i)
  22.   {
  23.     if(N%i==0)
  24.     {
  25.       long long K=N/i;
  26.       if(isprime(K))
  27.         M=(K>M)?K:M;
  28.       else if(isprime(i))
  29.         M=(i>M)?i:M;
  30.     }
  31.   }
  32.   cout<<M<<endl;
  33.   return 0;
  34. }

复制代码

这个程序在Ryzen5 3600的CPU的Unbuntu20.04系统上运行时间是:0.00867346秒,答案是:6857。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-12-30 20:25:47 | 显示全部楼层
接下来我们用OpenMP方式来对本程序进行加速,由于本身的数据不是很大,所以可能会出现运行时间不会降低有时反而增加的情况,但随着现在电子工业的发展,CPU全面向多核心方向发展(现在手机的CPU都基本上是8核),所以平行编程的学习是非常有性价比学习。
  1. #include <iostream>
  2. #include <cmath>
  3. #include <omp.h>
  4. using namespace std;

  5. const long long N=600851475143LL;
  6. const long long D=775146;

  7. inline bool isprime(long long n)
  8. {
  9.   if((n&1)==0)
  10.     return false;
  11.   long long d=(long long)sqrt((double)n);
  12.   for(long long i=3; i<=d; i+=2)
  13.   {
  14.     if(n%i==0)
  15.       return false;
  16.   }
  17.   return true;
  18. }

  19. int main(void)
  20. {
  21.   long long M=0;
  22.   #pragma omp parallel for reduction(max:M)
  23.   for(long long i=1; i<=D; ++i)
  24.   {
  25.     if(N%i==0)
  26.     {
  27.       long long K=N/i;
  28.       if(isprime(K))
  29.         M=(K>M)?K:M;
  30.       else if(isprime(i))
  31.         M=(i>M)?i:M;
  32.     }
  33.   }
  34.   cout<<M<<endl;
  35.   return 0;
  36. }

复制代码

这个程序在Ryzen5 3600的CPU的Unbuntu20.04系统上运行时间是:0.00175184秒,答案是:6857。从代码可以看出代码改变得并不多,但加速比却达到了:4.95。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-12-30 20:39:44 | 显示全部楼层
再接下来我们用GPU编程来加速这个程序,并通过这个例子来初步了解一下OpenACC,同样现在众核编程(通俗来讲就是在计算加速卡上进行计算的加速,显卡计算如:CUDA,OpenACC等)是国内大型计算机进行快速运算的一种主要手段所以会这样的计算将来就业的路子有多了一条。
  1. #include <iostream>
  2. #include <openacc.h>
  3. #include <cmath>
  4. using namespace std;

  5. const long long N=600851475143LL;
  6. const long long D=775146;

  7. #pragma acc routine
  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. int main(void)
  21. {
  22.   double t=omp_get_wtime();
  23.   long long M=0;
  24. #pragma acc kernels loop reduction(max:M)
  25.   for(long long i=1; i<=D; ++i)
  26.   {
  27.     if(N%i==0)
  28.     {
  29.       long long K=N/i;
  30.       if(isprime(K))
  31.         M=(K>M)?K:M;
  32.       else if(isprime(i))
  33.         M=(i>M)?i:M;
  34.     }
  35.   }
  36.   cout<<M<<t<<endl;
  37.   return 0;
  38. }

复制代码

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

使用道具 举报

发表于 2022-1-1 20:42:51 | 显示全部楼层
本帖最后由 guosl 于 2022-1-1 21:10 编辑

再接下来我们用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. const long long N = 600851475143LL;
  5. const long long D = 775146LL;
  6. const int nBlockDim = 128;
  7. const int nBlocks = 128;

  8. __device__ 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. __global__ void findprime(long long s, long long* r)
  21. {
  22.   __shared__ long long lm[nBlocks];
  23.   long long M = 0;
  24.   int n = s + threadIdx.x + blockIdx.x * nBlockDim;
  25.   if (n <= D)
  26.   {

  27.     if (N % n == 0)
  28.     {
  29.       long long K = N / n;
  30.       if (isprime(K))
  31.         M = (K > M) ? K : M;
  32.       else if (isprime(n))
  33.         M = (n > M) ? n : M;
  34.     }
  35.   }
  36.   lm[threadIdx.x] = M;
  37.   __syncthreads();
  38.   n = nBlockDim / 2;
  39.   while (n > 0)
  40.   {
  41.     if (threadIdx.x < n)
  42.     {
  43.       if (lm[threadIdx.x] < lm[threadIdx.x + n])
  44.         lm[threadIdx.x] = lm[threadIdx.x + n];
  45.     }
  46.     n /= 2;
  47.     __syncthreads();
  48.   }
  49.   if (threadIdx.x == 0)
  50.     r[blockIdx.x] = lm[0];
  51. }

  52. int main(void)
  53. {
  54.   long long* pM = NULL;
  55.   long long* p_dM = NULL;
  56.   long long s = 2, nMaxPrime = 2;
  57.   cudaError_t cudaStatus;
  58.   int nPId = 0;
  59.   cudaStatus = cudaSetDevice(nPId);//设置计算卡
  60.   if (cudaStatus != cudaSuccess)
  61.   {
  62.     fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
  63.     goto Error;
  64.   }
  65.   cudaDeviceProp deviceProp;
  66.   cudaStatus = cudaGetDeviceProperties(&deviceProp, nPId);
  67.   if (cudaStatus != cudaSuccess)
  68.     goto Error;
  69.   printf("GPU Device %d: "%s" with compute capability %d.%d\n\n", nPId, deviceProp.name, deviceProp.major, deviceProp.minor);
  70.   cudaStatus = cudaSetDevice(0);
  71.    //在主机上分配锁定内存
  72.   cudaStatus = cudaHostAlloc((void**)&pM, nBlocks * sizeof(long long), cudaHostAllocDefault);
  73.   if (cudaStatus != cudaSuccess)
  74.   {
  75.     fprintf(stderr, "CUDA alloc memory failed!");
  76.     goto Error;
  77.   }
  78. //在显卡上分配内存
  79.   cudaStatus = cudaMalloc((void**)&p_dM, nBlocks * sizeof(long long));
  80.   if (cudaStatus != cudaSuccess)
  81.   {
  82.     fprintf(stderr, "cudaMalloc failed!");
  83.     goto Error;
  84.   }
  85.   while (s <= D)
  86.   {
  87.     findprime << <nBlocks, nBlockDim >> > (s, p_dM);//进行显卡计算
  88.     cudaStatus = cudaGetLastError();
  89.     if (cudaStatus != cudaSuccess)
  90.     {
  91.       fprintf(stderr, "addKernel launch failed: %s\n", cudaGetErrorString(cudaStatus));
  92.       goto Error;
  93.     }
  94.     cudaStatus = cudaDeviceSynchronize();//等待显卡的计算完成
  95.     if (cudaStatus != cudaSuccess)
  96.     {
  97.       fprintf(stderr, "cudaDeviceSynchronize returned error code %d after launching addKernel!\n", cudaStatus);
  98.       goto Error;
  99.     }
  100.     cudaStatus = cudaMemcpy(pM, p_dM, nBlocks * sizeof(long long), cudaMemcpyDeviceToHost);//从显卡取回计算的结果
  101.     if (cudaStatus != cudaSuccess)
  102.     {
  103.       fprintf(stderr, "cudaMemcpy failed!");
  104.       goto Error;
  105.     }
  106.     for (int i = 0; i < nBlocks; ++i) //归并结果
  107.       nMaxPrime = (nMaxPrime > pM[i]) ? nMaxPrime : pM[i];
  108.     s += nBlocks * nBlockDim;
  109.   }
  110.   printf("%lld\n", nMaxPrime);
  111. Error:
  112.   if (p_dM != NULL)
  113.   {
  114.     cudaFree(p_dM);
  115.     p_dM = NULL;
  116.   }
  117.   if (pM != NULL)
  118.   {
  119.     cudaFreeHost(pM);
  120.     pM = NULL;
  121.   }
  122.   return 0;
  123. }
复制代码

运行时间是:0.001818秒,答案是:6857。在这里看来人工智能还是比不过了人工。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-10 12:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表