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

大天使 · 发表于 2016-8-11 00:11:06

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

始终 · 发表于 2016-8-12 02:24:20

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 · 发表于 2016-8-25 20:43:31

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]

鱼油小白 · 发表于 2016-9-6 16:54:30

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

复制代码

秒出结果

鱼油小白 · 发表于 2016-9-6 16:56:18

#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 · 发表于 2016-9-22 18:49:38

本帖最后由 dodopromi 于 2016-9-22 18:52 编辑

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 · 发表于 2016-9-27 15:21:32

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 · 发表于 2016-10-10 09:45:40

[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

复制代码

梦想绘制者 · 发表于 2016-11-2 18:48:39

本帖最后由梦想绘制者于 2016-11-2 18:54 编辑

# 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.

梦想绘制者 · 发表于 2016-11-2 19:30:12

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 · 发表于 2016-11-6 22:31:03

#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 · 发表于 2016-11-7 12:28:07

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 · 发表于 2016-11-15 22:38:45

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 · 发表于 2016-11-26 15:58:21

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丶 · 发表于 2016-12-4 20:40:31

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

芒果加黄桃 · 发表于 2017-1-6 12:37:24

本帖最后由芒果加黄桃于 2017-1-6 14:17 编辑

# 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))

复制代码

渡风 · 发表于 2017-1-22 13:06:02

此代码使用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 · 发表于 2017-1-22 15:06:37

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 · 发表于 2017-2-2 01:30:40

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 · 发表于 2017-2-16 20:29:12

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])

复制代码

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