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

大天使

我好像来到了一个神奇的地方

始终

import math

def is_prime(n):
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True


def max_prime(num):
    i = 2
    tmp = int(math.sqrt(num)) + 1
    m = n = 0
    while i <= tmp:
        if num % i == 0:
            if is_prime(i):
                n = i
            if is_prime(int(num / i)):
                m = int(num / i)
        i += 1
    if m != 0 or n != 0:
        return max(m, n)
    else:
        return None

print(max_prime(600851475143))

6857

Plusenxue

n = 600851475143
m = []
j = 2
while n != 1:
    for i in range(j,n+1):
        if n%i == 0:
            j = i
            m.append(i)
            break
    n = n//j

m[-1]

鱼油小白

#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long a = 600851475143;
    int i;
    for(i = 3;i <= a/3;)
        {
                if(a % i==0)
                {
                        a = a/i;
                }
                else
                {
                        i++;
                }
        }
        printf("%d\n",a);
}

秒出结果

鱼油小白

#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long a = 600851475143;
    int i;
    for(i = 3;i <= a/3;)
        {
                if(a % i==0)
                {
                        a = a/i;
                }
                else
                {
                        i++;
                }
        }
        printf("%d\n",a);
}

秒出结果

dodopromi

def maxy(n):  
    for i in range(2,n//2+1):  
        if n%i==0:
            print(int(n/i))  #这行把过程都写出来了，我要是只求答案，这行放外边，就变成none了
            return maxy(int(n/i))

n=int(input('请输入一个数:'))       
maxy(n)

有人帮帮我吗？中间的那个print放哪儿都不行啊。
现在的结果是

请输入一个数:600851475143
8462696833
10086647
6857
>>> 

但是要是我print领出来就报错  invalid character in identifier

if加else也加不来。 我要哭死了，大神们帮帮我也

toBeNot

public class LargestPrimeFactor 
{
        // 求一个数的最小素数因子
        public static long primeFactor(long n)
        {
                long i = 2L;
                while(n%i != 0)
                {
                        i++;
                }
                return i;
        }
        
        public static void main(String[] args)
        {
                long n = 600851475143L;
                
                // 最后跳出循环的n值为最大的素数因子
                while(primeFactor(n) != n)
                {
                        long f = primeFactor(n);
                        n = n / f;
                }
                
                System.out.println("所求数的最大素数因子为：" + n);        
        }
}

primeFactor函数的参数确定为long类型，总感觉不太合适，不知道大神门有没有好的改进？求不吝赐教。

jerryxjr1220

[71, 839, 1471, 6857L]
[Finished in 0.1s]

def devide(n,j=0):
        s = 0
        for i in range(2,int(n**0.5+1)):
                if n%i == 0:
                        s,j = n/i,i
                        break
        return (s,j)

lst = []
t = 600851475143
k,j = devide(t)[0],devide(t)[1]
while k != 0:
        lst.append(j)
        k,j = devide(k,j)[0],devide(k,j)[1]
for e in lst:
        f = t / e
        t = f
lst.append(f)
print lst

梦想绘制者

# Python 3.5 实现
# 求600851475143的最大质数因子
#
# 求解思路：
# 把整个问题分解成3个子问题，分别用函数实现
# 这3个子问题依次为：
# 1.求一个数的因子(序列)
# 2.判断一个数为质数
# 3.求一个序列的最大值

def Factors(n):
    f = []
    if n <= 1 or (not isinstance(n, int)):
        print('输入错误，请输入大于1的正整数！')
        return f
    else:
        half = int(n ** 0.5)
        for i in range(1,half + 1):
            if n % i == 0:
                f.append(i)
        return f
    
def isPrime(n):
    if n == 1:
        return False
    
    f = Factors(n)       
    if len(f) - 1 > 1:
        return False
    else:
        return True
  
def maxPrimeFactor(n):
    f = Factors(n)
    pf = []
    for each in f:
        if isPrime(each):
            pf.append(each)
    return max(f)

n = 600851475143
print('%d的最大质数因子为%d.'%(n, maxPrimeFactor(n)))

>>>
600851475143的最大质数因子为486847.

梦想绘制者

dodopromi 发表于 2016-9-22 18:49
有人帮帮我吗？中间的那个print放哪儿都不行啊。
现在的结果是

你这程序中因子应该是i而不是int(n/i)。我给你解释一下为什么输出这样的结果吧。

def maxy(n):  
    for i in range(2,n//2+1):  
        if n%i==0:
            print(int(n/i))  #这行把过程都写出来了，我要是只求答案，这行放外边，就变成none了
            return maxy(int(n/i))

n=int(input('请输入一个数:'))       
maxy(n)

你写的这个maxy()函数先一个for循环，其中要判断i是否是n的因子，是的话执行一条打印语句，同时还要在返回时调用这个函数自身，参数换成了int(n/i))也就是n是i的倍数。
你输入600851475143（奇数），调用maxy()函数。在i = 2的时候，n%2 == 0不满足。然后i变成了3，还不满足条件，直到第一个满足条件n%2 == 0的数i（71）为止，此时，你输出了一个int(n/i)也就是8462696833。然后return又调用maxy()函数，这次参数为int(n/i)也就是8462696833，然后又继续求8462696833与其第一个非1因子的商。如此继续下去。
你的程序可以这么改一下(但只是求n的最大因子，而没有质数的判断部分，你自己加上去吧)：

def maxy(n):
    f = []
    for i in range(2,n//2+1):
        if n%i == 0:
            f.append(i)
    return max(f)

n=int(input('请输入一个数：'))
maxy(n)

和vvv

#include<stdio.h>
#include<stdlib.h>


int main()
{
    long long a[100],num,i,n;
    printf("请输入一个正整数：  ");
    while(scanf("%I64d",&n))
    {
        num=0;
        for(i=2; i*i<=n; i++)
        {
            if(n%i==0)
                a[num++]=i;
            while(n%i==0)
                n/=i;
        }
        if(n>1)
            a[num++]=n;
        for(i=0; i<num; i++)
            printf("%I64d ",a[i]);
        printf("\n");
    }
    system("color 3f");
    return 0;
}

结果：
请输入一个正整数：  600851475143
71 839 1471 6857

tsembrace

import time
import math
def isPrime(n):
    if n<2:
        return False
    elif n==2:
        return True
    else:
        m=int(math.sqrt(n))
        for i in range(2,m+1):
            if n%i==0:
                return False
        return True

"""
思路：
从小到大逐数判断是否为因数，再判断该因数是否为质数，加入质因数列表
再判断该因数对应的因数是否为质数，如是，加入质因数列表
"""
def findMaxpn(n):
    list=[]
    m=int(math.sqrt(n))
    for i in range(2,m+1):
        if n%i==0:
            if isPrime(i):
                list.append(i)
            if isPrime(n/i):
                list.append(n/i)
    if list:
        list.sort()
        print(list)
        return list[-1]
    else:
        print("参数为质数，不符合条件！！")
        return 0

start1=time.clock()

print(findMaxpn(600851475143))

end1=time.clock()
print("方法一耗时"+str(end1-start1)+"s")
        

lyciam

def euler03(num=100):
    """
    13195的质数因子有5,7,13,29， 600851475143 的最大质数因子是多少
    """
    def isprime(n):
        if n%2 == 0: return False
        for x in range(3,int(n**0.5)+1,2):
            if n%x==0: return False
        else: return True

    def ismaxnum(n):
        tmp = []
        for i in range(3,int(n**0.5)+1,2):
            if isprime(i) and n%i == 0: tmp.append(i)
        return max(tmp)

    return ismaxnum(num)

print(euler03(600851475143))

参考了好多人的写法，自己再默写了一次

zhu244912654

import math


def IsPrime(n = 1):
    if n == 0:
        return False
    elif n == 1:
        return True
    elif n < 4:
        return True
    else:
        r = int(math.floor(math.sqrt(n)))
        for i in range(2,r+1):
            if n % i == 0:
                return False
        return True



def largestPrime(n):
    largest =0
    tmp = int(math.floor(math.sqrt(n)))
    for i in range((tmp),1,-1):
        #print('i = ',i)
        if IsPrime(i) and n%i == 0:
            largest = i
            break

    #print('largest = ',largest)
    return largest



print(largestPrime(600851475143 ))

Kan丶

python5行代码搞定 但是那运行效率真是日了狗

芒果加黄桃

# encoding:utf-8
# 600851475143 最大质数银子
from time import time
def isPrime(n):
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    sqr = int(n ** 0.5) 
    l_pn = [3]
    ispn = True
    while max(l_pn) < sqr:
        for i in range(max(l_pn) + 2, n, 2):
            ispn = True
            sqr_i = int(i ** 0.5) + 1
        
            for pn in l_pn:
                if i % pn == 0:
                    ispn = False
                    break
                if pn > sqr_i:
                    break
            if ispn:
                if n % i == 0:
                    return False;
                l_pn.append(i)
                break   
    return True

start = time()
number = 600851475143;
sqr_n = int(number ** 0.5)
for n in range(3, sqr_n):
    if number % n == 0:
        if isPrime(n):
            print('600851475143的质数因子包含：', str(n))
print('cost %.3f sec' % (time() - start))

渡风

此代码使用matlab编程
Problem3所用时间为0.58204秒
Problem3的答案为6857

%题目3：找出一个合数的最大质数因子  
function Output=Problem3(Input)
tic
if nargin==0
Input=600851475143;
end
for ii=floor(sqrt(Input)):-1:2
    temp=mod(Input,ii);
    if temp==0
        if Prime_Judge(ii)==1
            Output=ii;
            break
        end
    end
end
toc
disp('此代码使用matlab编程')
disp(['Problem3所用时间为',num2str(toc),'秒'])
disp(['Problem3的答案为',num2str(Output)])
end
%验证其是否为素数
%若输入为素数则Judge为1，否则为0
function Judge=Prime_Judge(Input)
if mod(Input,2)==0
    Judge=0;
elseif mod(Input,3)==0
    Judge=0;
else
    node=floor(sqrt(Input))+1;
    Judge=1;
    for ii=2:node
        if  mod(Input,ii)==0
            Judge=0;
            break
        else
        end
    end
end 
end

shinningpika

number=600851475143
a=[1]
b=1
c=1
def lung(number):
    for i in range(2,number):
        if number%i==0:
            a.append(i)
            break
while number*b==600851475143:
    lung(number)
    number=int(number/(a[-1]))
    b*=a[-1]
for each in a:
    c*=each
if a[-1]>(600851475143/c):
    print(a[-1])
else:
    print(600851475143/c)

很费劲。。找质数的循环写的太烂

FlySelf

import time
import math

def largest_prime_factor(number):
    '找出一个合数的最大质数因子'
    largest_factor = 1
    flag = True

    for i in range(2, int(math.sqrt(number))):
        if number % i == 0:
            for j in range(2, int(math.sqrt(i))):
                if i % j == 0:
                    flag = False
                    break
            if flag:
                largest_factor = i
                print(i)
            flag = True

    return largest_factor

start = time.clock()
print('600851475143的质数因子有：')
print('最大质数因子为%d' %largest_prime_factor(600851475143))
end = time.clock()
print('程序执行了%fs。' %(end - start))

执行结果：
600851475143的质数因子有：
71
839
1471
6857
最大质数因子为6857
程序执行了0.234420s。

piperacillin

from math import sqrt

def ifprime(n):
    k = 0
    if n == 1 or n == 0:
        k = 1
    elif n % 2 == 0 and n != 2:
        k = 1
    else:
        from math import sqrt
        maxi = int(sqrt(n))
        for i in range(3,maxi+1,2):
            if n % i == 0:
                k = 1
                break
    if k == 0:
        return True
    if k == 1:
        return False
    
def fact(num):
    f = []
    while True:
        maxi = int(sqrt(num))
        for i in range(2,maxi+1):
            if num % i == 0:
                f.append(int(i))
                num = num / i
                break
        if ifprime(num):
            f.append(int(num))
            break
        
    return f


if __name__ == '__main__':
    n = fact(600851475143)
    print(n[-1])