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

xg-sco · 发表于 2020-12-26 09:51:20

# 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 · 发表于 2021-3-6 10:49:34

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

int main(void)

int类型能存下600851475143吗？

酷爱语言的小白 · 发表于 2021-4-26 09:16:10

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 · 发表于 2021-5-3 17:41:08

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)

中国好青年 · 发表于 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))
这算法挺慢的，望大佬指点

卢本伟牛逼 · 发表于 2021-8-7 00:07:34

#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;
}

复制代码

鱼塘里的鱼儿 · 发表于 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++写的
每一个我都输出了

ft215378 · 发表于 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

番杰 · 发表于 2021-10-25 16:55:02

#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 · 发表于 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;
}

guosl · 发表于 2021-12-30 20:16:19

这个题目大家都能解出，有的效率高，有的效率就有待提高。但差别不大。下面我想通过几种不同的编程来介绍一下平行编程。
首先本题解决的最原始的编程方法是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 · 发表于 2021-12-30 20:25:47

接下来我们用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 · 发表于 2021-12-30 20:39:44

再接下来我们用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 · 发表于 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系统上编译运行的。

#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 · 发表于 2022-1-27 14:03:24

#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 · 发表于 2022-2-22 22:05:39

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 · 发表于 2022-3-16 15:27:43

本帖最后由 B1tetheDust 于 2022-3-16 15:46 编辑

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 · 发表于 2022-5-21 11:53:34

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)

开飞机的羊驼 · 发表于 2022-6-28 17:41:55

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 · 发表于 2022-8-8 11:15:20

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秒。

账号		自动登录	找回密码
密码			立即注册