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

xg-sco

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

int main ()
{
        long long int max = -1024;
        long long int num;
        printf("请输入一个数：");
        scanf("%lld", &num);
        
        for (int i = 2; i < sqrt(num); i++)
        {
                if (num % i == 0)
                {
                        printf("%d ", i);
                        if(i > max)
                        {
                                max = i;
                        }
                }
        }
        printf("\n");
        printf("max = %lld\n", max);
        
        return 0;
}

a1351468657

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

int main(void)

int类型能存下600851475143吗？

酷爱语言的小白

def factor_max(n):
    i = n-1
    while i < n:
        i += -1
        if n% i == 0:
            return i
n = 600851475143
i = 1
list1 = []
while i <= n:
    if n% i == 0 and factor_max(i) == 1:
        list1.append(i)
        print(i)
        n = n/ i
    i += 1

Kuri5u

target = 600851475143 
i = 2
result = []
while i<=target:
    if target%i==0:
        while target%i==0:
            target=target//i
        result.append(i)
    i+=1
print(result)        
        

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))
这算法挺慢的，望大佬指点

卢本伟牛逼

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

//target = 600851475143
unsigned long long int target = 600851475143;
static int count;

int find_max_prime_factor(unsigned long long int n)
{
        int i;
        
        for(i=(int)sqrt((double)n);i>=2;i--)
        {
                if (!(n%i)) return i;
                count += 1;
        }
        return 0;
}

int main(void)
{
        printf("result is %d\n", find_max_prime_factor(target));
        printf("count = %d\n", count);
        
        return 0;
}

鱼塘里的鱼儿

#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

番杰

#include<stdio.h>

#define MAX 600851475143L

int main(void)
{
        int flag = 0,max ;
        
        for(int i = 2;i<(MAX/2);i++)
        {
                flag = 0;
                if(MAX % i == 0)
                {
                        for(int j=2;j<(i/2);j++)
                        {
                                if(i % j == 0)
                                {
                                        flag = 1;
                                        break;
                                }
                        }
                        if(flag == 0)
                        {
                                max = i;
                        }
                }                 
        }

        printf("%d",max);
        
        return 0;
} 

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++。我的代码如下：

#include <iostream>
#include <cmath>
using namespace std;

const long long N=600851475143LL;
const long long D=775146;

bool isprime(long long n)
{
  if((n&1)==0)
    return false;
  long long d=(long long)sqrt((double)n);
  for(long long i=3; i<=d; i+=2)
  {
    if(n%i==0)
      return false;
  }
  return true;
}

int main(void)
{
  long long M=0;
  for(long long i=1; i<=D; ++i)
  {
    if(N%i==0)
    {
      long long K=N/i;
      if(isprime(K))
        M=(K>M)?K:M;
      else if(isprime(i))
        M=(i>M)?i:M;
    }
  }
  cout<<M<<endl;
  return 0;
}

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

guosl

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

#include <iostream>
#include <cmath>
#include <omp.h>
using namespace std;

const long long N=600851475143LL;
const long long D=775146;

inline bool isprime(long long n)
{
  if((n&1)==0)
    return false;
  long long d=(long long)sqrt((double)n);
  for(long long i=3; i<=d; i+=2)
  {
    if(n%i==0)
      return false;
  }
  return true;
}

int main(void)
{
  long long M=0;
  #pragma omp parallel for reduction(max:M)
  for(long long i=1; i<=D; ++i)
  {
    if(N%i==0)
    {
      long long K=N/i;
      if(isprime(K))
        M=(K>M)?K:M;
      else if(isprime(i))
        M=(i>M)?i:M;
    }
  }
  cout<<M<<endl;
  return 0;
}

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

guosl

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

#include <iostream>
#include <openacc.h>
#include <cmath>
using namespace std;

const long long N=600851475143LL;
const long long D=775146;

#pragma acc routine
bool isprime(long long n)
{
  if((n&1)==0)
    return false;
  long long d=(long long)sqrt((double)n);
  for(long long i=3; i<=d; i+=2)
  {
    if(n%i==0)
      return false;
  }
  return true;
}

int main(void)
{
  double t=omp_get_wtime();
  long long M=0;
#pragma acc kernels loop reduction(max:M)
  for(long long i=1; i<=D; ++i)
  {
    if(N%i==0)
    {
      long long K=N/i;
      if(isprime(K))
        M=(K>M)?K:M;
      else if(isprime(i))
        M=(i>M)?i:M;
    }
  }
  cout<<M<<t<<endl;
  return 0;
}

上面两个程序都是用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系统上编译运行的。

#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>

const long long N = 600851475143LL;
const long long D = 775146LL;
const int nBlockDim = 128;
const int nBlocks = 128;

__device__ bool isprime(long long n)
{
  if ((n & 1) == 0)
    return false;
  long long d = (long long)sqrt((double)n);
  for (long long i = 3; i <= d; i += 2)
  {
    if (n % i == 0)
      return false;
  }
  return true;
}

__global__ void findprime(long long s, long long* r)
{
  __shared__ long long lm[nBlocks];
  long long M = 0;
  int n = s + threadIdx.x + blockIdx.x * nBlockDim;
  if (n <= D)
  {

    if (N % n == 0)
    {
      long long K = N / n;
      if (isprime(K))
        M = (K > M) ? K : M;
      else if (isprime(n))
        M = (n > M) ? n : M;
    }
  }
  lm[threadIdx.x] = M;
  __syncthreads();
  n = nBlockDim / 2;
  while (n > 0)
  {
    if (threadIdx.x < n)
    {
      if (lm[threadIdx.x] < lm[threadIdx.x + n])
        lm[threadIdx.x] = lm[threadIdx.x + n];
    }
    n /= 2;
    __syncthreads();
  }
  if (threadIdx.x == 0)
    r[blockIdx.x] = lm[0];
}

int main(void)
{
  long long* pM = NULL;
  long long* p_dM = NULL;
  long long s = 2, nMaxPrime = 2;
  cudaError_t cudaStatus;
  int nPId = 0;
  cudaStatus = cudaSetDevice(nPId);//设置计算卡
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
    goto Error;
  }
  cudaDeviceProp deviceProp;
  cudaStatus = cudaGetDeviceProperties(&deviceProp, nPId);
  if (cudaStatus != cudaSuccess)
    goto Error;
  printf("GPU Device %d: "%s" with compute capability %d.%d\n\n", nPId, deviceProp.name, deviceProp.major, deviceProp.minor);
  cudaStatus = cudaSetDevice(0);
   //在主机上分配锁定内存
  cudaStatus = cudaHostAlloc((void**)&pM, nBlocks * sizeof(long long), cudaHostAllocDefault);
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "CUDA alloc memory failed!");
    goto Error;
  }
 //在显卡上分配内存
  cudaStatus = cudaMalloc((void**)&p_dM, nBlocks * sizeof(long long));
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "cudaMalloc failed!");
    goto Error;
  }
  while (s <= D)
  {
    findprime << <nBlocks, nBlockDim >> > (s, p_dM);//进行显卡计算
    cudaStatus = cudaGetLastError();
    if (cudaStatus != cudaSuccess)
    {
      fprintf(stderr, "addKernel launch failed: %s\n", cudaGetErrorString(cudaStatus));
      goto Error;
    }
    cudaStatus = cudaDeviceSynchronize();//等待显卡的计算完成
    if (cudaStatus != cudaSuccess)
    {
      fprintf(stderr, "cudaDeviceSynchronize returned error code %d after launching addKernel!\n", cudaStatus);
      goto Error;
    }
    cudaStatus = cudaMemcpy(pM, p_dM, nBlocks * sizeof(long long), cudaMemcpyDeviceToHost);//从显卡取回计算的结果
    if (cudaStatus != cudaSuccess)
    {
      fprintf(stderr, "cudaMemcpy failed!");
      goto Error;
    }
    for (int i = 0; i < nBlocks; ++i) //归并结果
      nMaxPrime = (nMaxPrime > pM[i]) ? nMaxPrime : pM[i];
    s += nBlocks * nBlockDim;
  }
  printf("%lld\n", nMaxPrime);
Error:
  if (p_dM != NULL)
  {
    cudaFree(p_dM);
    p_dM = NULL;
  }
  if (pM != NULL)
  {
    cudaFreeHost(pM);
    pM = NULL;
  }
  return 0;
}

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

mathtimes

#include <cstdio>
#include <cmath>
#include <vector>
using std::vector;
int main()
{
    vector<long long> factor;
    long long num = 600851475143;
    int i = 2;
    while(1)
    {
        for(i=2;i<sqrt(num)+1;i++)
        {
            if(num%i==0)
            {
                factor.push_back(i);
                num /= i;
                goto continuetodo;
            }
        }
        factor.push_back(num);
        break;
        continuetodo:;
    }
    long long max = 0;
    vector<long long>::iterator it;
    for(it=factor.begin();it!=factor.end();it++)
        if(*it>max)
            max = *it;
    printf("%d",max);
}

jerryxjr1220

package main

import (
        "fmt"
        "math"
        "time"
)

//题目3：
//
//13195 的质数因子有 5, 7, 13 和 29。
//
//600851475143 的最大质数因子是多少？
func main() {
        t := time.Now()
        limit := int64(math.Sqrt(600851475143))
        var remain int64 = 600851475143
        var max int64 = 2
        var i int64
        fmt.Println("分解质因数：")
        for i = 2; i < limit; i++ {
                if remain%i == 0 {
                        remain /= i
                        fmt.Println(i)
                        if i > max {
                                max = i
                        }
                        i = 2
                }
        }
        if remain > max {
                max = remain
        }
        fmt.Println("最大质因数是： ", max)
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

GOROOT=C:\Program Files\Go #gosetup
GOPATH=C:\Users\Administrator\go #gosetup
"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
C:\Users\Administrator\AppData\Local\Temp\GoLand\___2go_build_GoProject_src.exe
分解质因数：
71                   
839                  
1471                 
6857                 
最大质因数是：  6857 
耗时： 2 ms          

进程 已完成，退出代码为 0

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

B1tetheDust

import math
import time


class FindPrimeFactor:

    def __init__(self, num):
        self.num = self.max_prime = num
        self.find_factor()
        print(self.max_prime)

    @staticmethod
    def find_prime(a_num):
        is_prime = 1
        for i in range(2, int(math.sqrt(a_num) + 1)):
            if a_num % i == 0:
                is_prime = 0
        return is_prime

    def find_factor(self):
        divisor = int(math.sqrt(self.num))
        while (divisor - 1):
            if self.num % divisor == 0:
                if self.find_prime(divisor):
                    self.max_prime = divisor
                    break
            divisor -= 1


start = time.perf_counter()
test = FindPrimeFactor(600851475143)
end = time.perf_counter()
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

use rayon::prelude::*;
use std::time::Instant;

const N: i64 = 600851475143;

fn main() {
    let now = Instant::now();
    let primes = make_prime();
    let num = primes
    .into_par_iter()
    .filter(|x| N % x == 0)
    .max()
    .unwrap();
    println!("{}", num);
    println!("耗时{}秒。", now.elapsed().as_secs_f32())
}

fn make_prime() -> Vec<i64> {
    let mut primes = Vec::new();
    let mut cur = 10;
    // bootstrap
    for i in 2..cur {
        if primes.iter().all(|p| i % p != 0) {
            primes.push(i);
        }
    }
    let n = (N as f64).sqrt() as i64 + 1;
    while cur < n {
        let next = std::cmp::min(cur * cur, n);
        let mut addition: Vec<_> = (cur..next)
            .into_par_iter()
            .filter(|x| {
                for p in primes.iter() {
                    if x % p == 0 {
                        return false;
                    }
                    if x / p < *p {
                        break;
                    }
                }
                true
            })
            .collect();
        primes.append(&mut addition);
        cur = next;
    }
    primes
}

6857
耗时0.008448秒。