鱼C论坛

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

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

  [复制链接]
发表于 2020-5-12 10:33:33 | 显示全部楼层
用一切办法去减少程序时间,但是任然跑了有一分多钟(中途会输出一下)
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;

  4. bool isprime(unsigned long long int x)
  5. {
  6.         int last = sqrt(double(x));
  7.         for(unsigned long long int i=2; i<=last; i++)
  8.         {
  9.                 if(x%i == 0)
  10.                 {
  11.                         return false;
  12.                 }
  13.         }
  14.         return true;
  15. }

  16. int main()
  17. {
  18.         unsigned long long int num = 600851475143;
  19.         for(unsigned long long int i=sqrt(num)+1; i>=2; i -= 2)
  20.         {
  21.                 cout<<i<<' '<<isprime(i)<<endl;
  22.                 if(isprime(i))
  23.                 {
  24.                         if(num%i == 0)
  25.                         {
  26.                                 cout<<i;
  27.                                 return 0;
  28.                         }
  29.                 }
  30.         }
  31.         return 0;
  32. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-17 23:23:16 | 显示全部楼层
liuzhengyuan 发表于 2020-5-12 10:33
用一切办法去减少程序时间,但是任然跑了有一分多钟(中途会输出一下)

不妨调换一下 if(num%i == 0) 和 if(isprime(i)) 的位置。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-18 20:44:40 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-7-17 23:23
不妨调换一下 if(num%i == 0) 和 if(isprime(i)) 的位置。

谢谢,成功了!
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;

  4. bool isprime(unsigned long long int x)
  5. {
  6.         int last = sqrt(double(x));
  7.         for(unsigned long long int i=2; i<=last; i++)
  8.         {
  9.                 if(x%i == 0)
  10.                 {
  11.                         return false;
  12.                 }
  13.         }
  14.         return true;
  15. }

  16. int main()
  17. {
  18.         unsigned long long int num = 600851475143;
  19.         for(unsigned long long int i=sqrt(num)+1; i>=2; i -= 2)
  20.         {
  21.                 if(num%i == 0)
  22.                 {
  23.                         if(isprime(i))
  24.                         {
  25.                                 cout<<i;
  26.                                 return 0;
  27.                         }
  28.                 }
  29.         }
  30.         return 0;
  31. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-22 15:11:44 | 显示全部楼层
幻世伽蓝 发表于 2016-7-4 16:05
71/839/1471/6857   之后就没有反应了

加一步判断就好了,如果找到的质因子乘积等于给定的合数,就停止寻找,因为给的数太大,如果规定停止查找的条件,程序会有不必要的运行时间
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-22 15:14:20 | 显示全部楼层

judgePrimes(2) 的结果不对
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-28 01:38:06 | 显示全部楼层
  1. package main

  2. import (
  3.         "fmt"
  4.         "math"
  5.         "time"
  6. )

  7. func max(s []int) (max int) {
  8.         max = s[0]
  9.         for _, v := range s {
  10.                 if v > max {
  11.                         max = v
  12.                 }
  13.         }
  14.         return
  15. }

  16. func isPrime(n int) bool {
  17.         if n == 2 || n == 3 || n == 5 {
  18.                 return true
  19.         }
  20.         if n%6 != 1 && n%6 != 5 {
  21.                 return false
  22.         }
  23.         rt := int(math.Sqrt(float64(n)))
  24.         for i := 5; i <= rt; i += 6 {
  25.                 if n%i == 0 || n%(i+2) == 0 {
  26.                         return false
  27.                 }
  28.         }
  29.         return true
  30. }

  31. func getNextPrime(n int) int {
  32.         var result int
  33.         for {
  34.                 if isPrime(n + 1) {
  35.                         result += n
  36.                         break
  37.                 } else {
  38.                         n++
  39.                 }
  40.         }
  41.         return result + 1
  42. }

  43. func run(x int) []int {
  44.         var prime int = 2
  45.         primeFactor := []int{}
  46.         for isPrime(x) == false {
  47.                 if x%prime == 0 {
  48.                         x /= prime
  49.                         primeFactor = append(primeFactor, prime)
  50.                 }
  51.                 if x%prime != 0 {
  52.                         prime = getNextPrime(prime)
  53.                 }
  54.         }
  55.         if isPrime(x) == true {
  56.                 primeFactor = append(primeFactor, x)
  57.         }
  58.         return primeFactor
  59. }

  60. func main() {
  61.         bT := time.Now()

  62.         a := run(600851475143)
  63.         b := max(a)
  64.         fmt.Println(b)
  65.         fmt.Println(a)

  66.         eT := time.Since(bT)
  67.         fmt.Println("\n------------------------")
  68.         fmt.Println("Run time:", eT)
  69. }
复制代码

  1. 6857
  2. [71 839 1471 6857]

  3. ------------------------
  4. Run time: 1.027487ms
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-9 03:31:44 | 显示全部楼层
用时在0.05毫秒以内
发现前面很多答案虽然算出了这道题,但是缺乏泛用性,例如当数字为素数时会报错,有些答案甚至换一个题目数字时会给出非素数为答案。

用的是完全阶乘的算法。算素数的部分也没有使用算数模块(但是速度没有影响)

  1. import time
  2. starttime = time.time()
  3. ##########################用时检测##################
  4. def isprime(number):
  5.     if number < 2:
  6.         return False
  7.     if number % 2 ==0:
  8.         return False
  9.     if number == 3:                         #不得不加上这句,否则会认为3是素数
  10.         return True
  11.     divider = 3
  12.     proxy1 = number
  13.     while divider <= proxy1:                #每次除法时,商被用作与下一个除数比较,这样子可以加快计算速度
  14.         if number % divider == 0:           #没有用到sqrt但是计算速度几乎一样(也许sqrt的本质也就是如此)。。。
  15.             return False
  16.             
  17.         proxy1 = int(number/divider)
  18.         divider += 2

  19.     return True

  20.    
  21. def lpf(number):                            #阶乘法
  22.     proxy = number
  23.     if isprime(proxy):                      #先检查是不是质数,否则慢死
  24.         print(proxy)
  25.         return

  26.     while proxy % 2 == 0:                   #2开始阶乘
  27.         proxy = proxy / 2
  28.         if proxy == 1:                      #如果是2的n次幂那就是2
  29.             print(2)
  30.             return
  31.             
  32.    
  33.     divider = 3                             #然后是3开始阶乘
  34.     while divider <= (number/2):            
  35.             
  36.         
  37.         
  38.         if isprime(divider):                #检查除数是否为素数
  39.             while proxy % divider == 0:     
  40.                 proxy = proxy / divider

  41.                 if isprime(proxy):          #检查剩下的数是否为素数
  42.                     print(proxy)
  43.                     return

  44.                 elif proxy == 1:            #结束语句。当阶乘的商为1的时候就结束了
  45.                     print(divider)          #打印最后一个除数即为最大素数因数
  46.                     return
  47.                
  48.             divider += 2                    #每次除数+2进行素数判断


  49.         else:
  50.             divider += 2                    #不是素数的话直接+2


  51. lpf(600851475143)


  52. ##########################
  53. endtime = time.time()
  54. print(endtime - starttime)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-9 08:53:51 | 显示全部楼层
KingFish-v- 发表于 2020-8-9 03:31
用时在0.05毫秒以内
发现前面很多答案虽然算出了这道题,但是缺乏泛用性,例如当数字为素数时会报错,有些 ...

判断质数是完全可以省去的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-10 13:00:04 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-8-9 08:53
判断质数是完全可以省去的。

我想了想,确实判断除数是否为质数是可以去掉的(不是质数肯定不会除尽。。)。去掉后运行速度达到了0.003秒上下。

但是感觉判断每次阶乘后的商和判断题目数字本身是否为质数的步骤不能省略。否则万一碰到题目就是一个大质数,或者经过一两次阶乘后就已得到最大质数因子的情况,运行速度就会变慢很多。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-10 13:12:06 | 显示全部楼层
KingFish-v- 发表于 2020-8-10 13:00
我想了想,确实判断除数是否为质数是可以去掉的(不是质数肯定不会除尽。。)。去掉后运行速度达到了0.00 ...

并不。你的判断质数的函数跟阶乘法一样慢。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-10 19:30:49 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-8-10 13:12
并不。你的判断质数的函数跟阶乘法一样慢。

我看了老哥在85楼给出的python答案

  1. num = 600851475143
  2. divisor = 3

  3. while num != 1:
  4.     if num % divisor:
  5.         divisor += 2
  6.     else:
  7.         num //= divisor

  8. print(divisor)
复制代码


虽然很简练,但是如果题目的数字是个偶数的话就跑不出来的样子。如果是素数的话(我用的一直是99998441),就要跑5秒多。就算按照题目的说法是找一个合数的最大质数,那用299995323(也就是99998441的三倍),也是要花5秒多。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 15:28:05 | 显示全部楼层
百度质数因= =,我懵了- -~跳过~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 16:05:10 | 显示全部楼层
yhhpf 发表于 2020-8-21 15:28
百度质数因= =,我懵了- -~跳过~

小学就讲过的啊……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 16:05:44 | 显示全部楼层
KingFish-v- 发表于 2020-8-10 19:30
我看了老哥在85楼给出的python答案

哦,这个版本没有优化,而且不是通用的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-21 16:36:56 | 显示全部楼层

小学讲过太多东西了,都忘了,哈哈。
回头再看回头再看~~~
想知道小甲鱼最近在做啥?请访问 -> 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))
复制代码

前面还在算质数...我天...算半天...
想知道小甲鱼最近在做啥?请访问 -> 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.")
复制代码
想知道小甲鱼最近在做啥?请访问 -> 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))
想知道小甲鱼最近在做啥?请访问 -> 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
想知道小甲鱼最近在做啥?请访问 -> 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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-28 19:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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