题目3：找出一个合数的最大质数因子,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

渡风发表于 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
   ifmod(Input,ii)==0
         Judge=0;
         break
   else
   end
end
end
end

shinningpika 发表于 2017-1-22 15:06:37

number=600851475143
a=
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])

0mrli0 发表于 2017-2-20 07:00:43

本帖最后由 0mrli0 于 2017-2-20 07:02 编辑

/*找一个合数的最大质数因子
600851475143的最大质数因子是多少？
分析：先分解质因式，再输出最大结果。*/

#include <stdio.h>
#define N 600851475143

int main()
{
unsigned long long i, maxfactor;
unsigned long long n = N;
for(i=2; i<=n; i++)
{
   while(n%i == 0)
   {
         printf("%u ", i);
         n = n / i;
         maxfactor = n==1 ? maxfactor : n;
   }
}
printf("\nmaxfactor = %u\n",maxfactor);
return 0;
}
71 839 1471 6857
maxfactor = 6857

Process returned 0 (0x0) execution time : 0.014 s

marmot 发表于 2017-2-20 21:12:25

print("""问题： 13195 的质数因子有 5, 7, 13 和 29。
600851475143 的最大质数因子是多少？
-------------------------------------------------""")

# 数字除以2，若能被整除，取结果继续除以 i = 2，若不能则除以 i+1：
# 依序递增，直到被自己除，此时的数字即为所求的最大质因子。

def zhiyinzi(x):
i=2
while x != 1 :          # x 不等于 1
   if x % i == 0:       # 能除尽2
         x = x/i             # 继续除
         zhiyinzi = i       # 得到最大质因子
   else:
         i += 1                # 除不尽就 +1

returnzhiyinzi

print("答案是： " + str(zhiyinzi(600851475143)))

6leensky 发表于 2017-2-25 15:34:38

n = 600851475143
i = 2
while i <= n/2: # 最大的质因数不大于被2除后的商
while n%i == 0: #能被i除尽
   n = n/i #能被i除尽，将商赋予n，继续除，直至除尽重复的约数
i += 1       #若除不尽，i＋1，外侧循环
print(n)          #直至最后，约数是其本身，则为质因数，且最大

我的答案是 6857
也有其他鱼油推荐了，能够可视化python程序执行的网站，再推荐之 http://www.pythontutor.com/

pan1990 发表于 2017-2-27 11:16:19

def pm(n):
if n==1:
   return 1
else:
      for i in range(1,((n//2)+1)):
         if n%i ==0:
               #print(i)
               n=n//i
               return (pm(n))
      else:
            return n

余欲渔 发表于 2017-3-1 16:05:45

不严谨的解法
zhishu=
def jc(i):
for x in zhishu:
   if i%x==0:return 1
for i in range(5,10000,2):
if jc(i):continue
if i not in zhishu:zhishu.append(i)
zhishu.reverse()
for i in zhishu:
if 600851475143%i==0:
   print(i)
   break

>>>
== RESTART: C:\Users\ASUS\AppData\Local\Programs\Python\Python35-32\test.py ==
6857

夜魔时生 发表于 2017-3-6 11:26:16

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

99592938 发表于 2017-3-14 11:54:35

Liu_xy 发表于 2016-5-4 22:23
6857

read:0.209758 s

int(math.sqrt(x)要+1，不然你试试13195？

翼-- 发表于 2017-3-20 17:13:31

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

int main()
{
long long num = 0;
printf("***input the number:\n");
scanf("%lld",&num);
long long flag = 0; //存放最大质因数

//对于偶合数先进行转换成奇数操作
while(num % 2 == 0)
{
num = num / 2;
flag = 2;
}

//对于奇合数进行操作，模上从3开始的奇数
while(1)
{
if(num % i == 0)
{
//对于合数中的因数进行质数判断，是质数的存放到flag中
long long j = 2;
for(; j <= i / 2; j++){
if(i % j == 0)
break;
}
if(j > i / 2){
flag = i;
num = num / i;
}
}
if(num < i)
break;
i = i + 2;
}
printf("***the largest prime factor is %lld",flag);
}

JonTargaryen 发表于 2017-3-26 16:40:54

#include <stdio.h>
#include <math.h>

int main(void)
{
long int number;
int factor;

// number = 13195;
number = 600851475143;

for(factor = 2; factor <= sqrt(number); factor++)
{
   if(!(number % factor))
   {
         number /= factor;
         printf("%d ", factor);
   }
}
printf("\n");

printf("%ld\n", number);

return 0;
}

JonTargaryen 发表于 2017-3-26 16:42:11

import math

# number = 13195
number = 600851475143

factor = 2
largest = int(math.sqrt(number))

while factor <= largest:
if not (number % factor):
   number /= factor
   print(factor, end = ' ')

   factor = 1
   largest = int(math.sqrt(number))

factor += 1

print("\nThe largest prime factor is:", int(number))

Eagle.Tong 发表于 2017-4-16 02:03:19

本帖最后由 Eagle.Tong 于 2017-4-16 02:12 编辑

Python
#求600851475143的最大质数因子

import math
import time

def ifprime(n):
   r = int(math.sqrt(n))
   for i in range(2,r+1):
         if n%i == 0:
            return 0
   return 1

start = time.time()
number = 600851475143
dividend = int(math.sqrt(number)) + 1
Flag = 0
while dividend > 1:
if number%dividend == 0:
   Flag = ifprime(dividend)
   if Flag == 1:
         print(dividend)
         break
dividend -= 1

end = time.time()
print(end-start)

6857
0.4s

天之南 发表于 2017-4-30 18:58:06

#include<stdio.h>

int main(void)
{
long long x = 600851475143;
long long maxF = x;
for (int i = 2; i * i < maxF; i++)
{
while (maxF%i == 0) {
maxF /= i;
}
}
printf("%ld\n", maxF);

return 0;
}

铭记太阳 发表于 2017-5-4 13:15:57

答案是688543

我的代码非常简单，借助比较好的思路；将Num从2到Num/2往下除，如果能除2就循环除2直到除不动为止，同时Num借此机会可以迅速缩小，缩小的结果不但计算变快，同时2到Num/2的范围也在急速缩小，把小因数都除完最后剩下的大块就是最大的因数了。

#include<stdio.h>

int main(void)
{
int i;
unsigned long Num=600851475143;
for(i=2;i<(Num/2);++i)
{
if(Num%i==0)
{
while(Num%i==0) Num=Num/i;
}
}
printf("%d\n",Num);
return 0;
}

俞晨曦 发表于 2017-6-20 23:43:15

bool IsPrime(int num)
{
int count = (int)sqrt(num);
int flag = 0;

for (int i = 2;i <= count && !flag;++i)
{
if(num % i == 0)
flag = 1;
}
if(flag)
return false;
else
return true;
}

int three(int num)
{
int fact = 1;

for(int i = 2;i <= num - 1;++i)
{
if(num % i == 0 && i > fact && IsPrime(i))
fact = i;
}
return fact;
}

水冢发表于 2017-8-21 23:06:02

#include <stdio.h>

int main(void){

   int prime, i;
   long long int n = 600851475143;
   for (i = 2; i < n; i++){
            if (n / i == 0){
                     break;
            }else if (n % i == 0){
                     n = n / i;
            }
   }

   printf("answer = %d", i);
   return 0;
}

BngThea 发表于 2017-9-8 15:02:38

def checkprime(target):
for i in range(2,int(target/2 + 1)):
   if not(target % i):
         return False
   elif i > int(target/2 - 1):
         return True

def maxprime(tar):
fact = int(tar/2 + 1)
while fact > 2:
   if not(tar % fact):
         if checkprime(fact):
            break
   fact -= 1
print(str(tar)+'的最大质数因子是：' + str(fact))
#maxprime(5555)
maxprime(600851475143)

页: 1 2 [3] 4 5 6 7 8

鱼C论坛's Archiver