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

liuzhengyuan

用一切办法去减少程序时间，但是任然跑了有一分多钟（中途会输出一下）

#include<iostream>
#include<math.h>
using namespace std;

bool isprime(unsigned long long int x)
{
        int last = sqrt(double(x));
        for(unsigned long long int i=2; i<=last; i++)
        {
                if(x%i == 0)
                {
                        return false;
                }
        }
        return true;
}

int main()
{
        unsigned long long int num = 600851475143;
        for(unsigned long long int i=sqrt(num)+1; i>=2; i -= 2)
        {
                cout<<i<<' '<<isprime(i)<<endl;
                if(isprime(i))
                {
                        if(num%i == 0)
                        {
                                cout<<i;
                                return 0;
                        }
                }
        }
        return 0;
}

永恒的蓝色梦想

liuzhengyuan 发表于 2020-5-12 10:33
用一切办法去减少程序时间，但是任然跑了有一分多钟（中途会输出一下）

不妨调换一下 if(num%i == 0) 和 if(isprime(i)) 的位置。

liuzhengyuan

永恒的蓝色梦想 发表于 2020-7-17 23:23
不妨调换一下 if(num%i == 0) 和 if(isprime(i)) 的位置。

谢谢，成功了！

#include<iostream>
#include<math.h>
using namespace std;

bool isprime(unsigned long long int x)
{
        int last = sqrt(double(x));
        for(unsigned long long int i=2; i<=last; i++)
        {
                if(x%i == 0)
                {
                        return false;
                }
        }
        return true;
}

int main()
{
        unsigned long long int num = 600851475143;
        for(unsigned long long int i=sqrt(num)+1; i>=2; i -= 2)
        {
                if(num%i == 0)
                {
                        if(isprime(i))
                        {
                                cout<<i;
                                return 0;
                        }
                }
        }
        return 0;
}

xuan1788

幻世伽蓝 发表于 2016-7-4 16:05
71/839/1471/6857   之后就没有反应了

加一步判断就好了，如果找到的质因子乘积等于给定的合数，就停止寻找，因为给的数太大，如果规定停止查找的条件，程序会有不必要的运行时间

xuan1788

过河的小卒 发表于 2016-7-18 15:28
71
839
1471

judgePrimes(2) 的结果不对

Wesleyz

package main

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

func max(s []int) (max int) {
        max = s[0]
        for _, v := range s {
                if v > max {
                        max = v
                }
        }
        return
}

func isPrime(n int) bool {
        if n == 2 || n == 3 || n == 5 {
                return true
        }
        if n%6 != 1 && n%6 != 5 {
                return false
        }
        rt := int(math.Sqrt(float64(n)))
        for i := 5; i <= rt; i += 6 {
                if n%i == 0 || n%(i+2) == 0 {
                        return false
                }
        }
        return true
}

func getNextPrime(n int) int {
        var result int
        for {
                if isPrime(n + 1) {
                        result += n
                        break
                } else {
                        n++
                }
        }
        return result + 1
}

func run(x int) []int {
        var prime int = 2
        primeFactor := []int{}
        for isPrime(x) == false {
                if x%prime == 0 {
                        x /= prime
                        primeFactor = append(primeFactor, prime)
                }
                if x%prime != 0 {
                        prime = getNextPrime(prime)
                }
        }
        if isPrime(x) == true {
                primeFactor = append(primeFactor, x)
        }
        return primeFactor
}

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

        a := run(600851475143)
        b := max(a)
        fmt.Println(b)
        fmt.Println(a)

        eT := time.Since(bT)
        fmt.Println("\n------------------------")
        fmt.Println("Run time:", eT)
}

6857
[71 839 1471 6857]

------------------------
Run time: 1.027487ms

KingFish-v-

用时在0.05毫秒以内
发现前面很多答案虽然算出了这道题，但是缺乏泛用性，例如当数字为素数时会报错，有些答案甚至换一个题目数字时会给出非素数为答案。

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

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

    return True

    
def lpf(number):                            #阶乘法
    proxy = number
    if isprime(proxy):                      #先检查是不是质数，否则慢死
        print(proxy)
        return

    while proxy % 2 == 0:                   #2开始阶乘
        proxy = proxy / 2
        if proxy == 1:                      #如果是2的n次幂那就是2
            print(2)
            return
            
    
    divider = 3                             #然后是3开始阶乘
    while divider <= (number/2):            
             
        
        
        if isprime(divider):                #检查除数是否为素数
            while proxy % divider == 0:     
                proxy = proxy / divider

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

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


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


lpf(600851475143)


##########################
endtime = time.time()
print(endtime - starttime)

永恒的蓝色梦想

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

判断质数是完全可以省去的。

KingFish-v-

永恒的蓝色梦想 发表于 2020-8-9 08:53
判断质数是完全可以省去的。

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

但是感觉判断每次阶乘后的商和判断题目数字本身是否为质数的步骤不能省略。否则万一碰到题目就是一个大质数，或者经过一两次阶乘后就已得到最大质数因子的情况，运行速度就会变慢很多。

永恒的蓝色梦想

KingFish-v- 发表于 2020-8-10 13:00
我想了想，确实判断除数是否为质数是可以去掉的（不是质数肯定不会除尽。。）。去掉后运行速度达到了0.00 ...

并不。你的判断质数的函数跟阶乘法一样慢。

KingFish-v-

永恒的蓝色梦想 发表于 2020-8-10 13:12
并不。你的判断质数的函数跟阶乘法一样慢。

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

num = 600851475143
divisor = 3

while num != 1:
    if num % divisor:
        divisor += 2
    else:
        num //= divisor

print(divisor)

虽然很简练，但是如果题目的数字是个偶数的话就跑不出来的样子。如果是素数的话（我用的一直是99998441），就要跑5秒多。就算按照题目的说法是找一个合数的最大质数，那用299995323（也就是99998441的三倍），也是要花5秒多。

yhhpf

百度质数因= =，我懵了- -~跳过~

永恒的蓝色梦想

yhhpf 发表于 2020-8-21 15:28
百度质数因= =，我懵了- -~跳过~

小学就讲过的啊……

永恒的蓝色梦想

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

哦，这个版本没有优化，而且不是通用的。

yhhpf

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

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

yhhpf

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

是我想太多

a = 600851475143
l = []
while a != 1:
    for i in range(2, a + 1):
        if a % i == 0:
            l.append(i)
            a = a // i
            break
print(l)
print(max(l))

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

永恒的蓝色梦想

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

这个是通用版：

def maxPrimeDivisor(num: int) -> int:
    if isinstance(num, int):
        if num < 2:
            raise ValueError("No prime divisor.")

        while not num & 1:
            num >>= 1

        if num == 1:
            return 2

        max = num ** 0.5
        divisor = 3

        while divisor <= max:
            if num % divisor:
                divisor += 2
                
            else:
                num //= divisor

                while not num % divisor:
                    num //= divisor

                if num == 1:
                    return divisor
                
                max = num ** 0.5

        return num

    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)