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

渡风

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

1. %题目3：找出一个合数的最大质数因子  
   
2. function Output=Problem3(Input)
   
3. tic
   
4. if nargin==0
   
5. Input=600851475143;
   
6. end
   
7. for ii=floor(sqrt(Input)):-1:2
   
8.     temp=mod(Input,ii);
   
9.     if temp==0
   
10.         if Prime_Judge(ii)==1
    
11.             Output=ii;
    
12.             break
    
13.         end
    
14.     end
    
15. end
    
16. toc
    
17. disp('此代码使用matlab编程')
    
18. disp(['Problem3所用时间为',num2str(toc),'秒'])
    
19. disp(['Problem3的答案为',num2str(Output)])
    
20. end
    
21. %验证其是否为素数
    
22. %若输入为素数则Judge为1，否则为0
    
23. function Judge=Prime_Judge(Input)
    
24. if mod(Input,2)==0
    
25.     Judge=0;
    
26. elseif mod(Input,3)==0
    
27.     Judge=0;
    
28. else
    
29.     node=floor(sqrt(Input))+1;
    
30.     Judge=1;
    
31.     for ii=2:node
    
32.         if  mod(Input,ii)==0
    
33.             Judge=0;
    
34.             break
    
35.         else
    
36.         end
    
37.     end
    
38. end
    
39. end
    

复制代码

shinningpika

1. number=600851475143
   
2. a=[1]
   
3. b=1
   
4. c=1
   
5. def lung(number):
   
6.     for i in range(2,number):
   
7.         if number%i==0:
   
8.             a.append(i)
   
9.             break
   
10. while number*b==600851475143:
    
11.     lung(number)
    
12.     number=int(number/(a[-1]))
    
13.     b*=a[-1]
    
14. for each in a:
    
15.     c*=each
    
16. if a[-1]>(600851475143/c):
    
17.     print(a[-1])
    
18. else:
    
19.     print(600851475143/c)
    

复制代码

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

FlySelf

1. import time
   
2. import math
   
3. 
   
4. def largest_prime_factor(number):
   
5.     '找出一个合数的最大质数因子'
   
6.     largest_factor = 1
   
7.     flag = True
   
8. 
   
9.     for i in range(2, int(math.sqrt(number))):
   
10.         if number % i == 0:
    
11.             for j in range(2, int(math.sqrt(i))):
    
12.                 if i % j == 0:
    
13.                     flag = False
    
14.                     break
    
15.             if flag:
    
16.                 largest_factor = i
    
17.                 print(i)
    
18.             flag = True
    
19. 
    
20.     return largest_factor
    
21. 
    
22. start = time.clock()
    
23. print('600851475143的质数因子有：')
    
24. print('最大质数因子为%d' %largest_prime_factor(600851475143))
    
25. end = time.clock()
    
26. print('程序执行了%fs。' %(end - start))
    

复制代码

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

piperacillin

1. from math import sqrt
   
2. 
   
3. def ifprime(n):
   
4.     k = 0
   
5.     if n == 1 or n == 0:
   
6.         k = 1
   
7.     elif n % 2 == 0 and n != 2:
   
8.         k = 1
   
9.     else:
   
10.         from math import sqrt
    
11.         maxi = int(sqrt(n))
    
12.         for i in range(3,maxi+1,2):
    
13.             if n % i == 0:
    
14.                 k = 1
    
15.                 break
    
16.     if k == 0:
    
17.         return True
    
18.     if k == 1:
    
19.         return False
    
20.    
    
21. def fact(num):
    
22.     f = []
    
23.     while True:
    
24.         maxi = int(sqrt(num))
    
25.         for i in range(2,maxi+1):
    
26.             if num % i == 0:
    
27.                 f.append(int(i))
    
28.                 num = num / i
    
29.                 break
    
30.         if ifprime(num):
    
31.             f.append(int(num))
    
32.             break
    
33.         
    
34.     return f
    
35. 
    
36. 
    
37. if __name__ == '__main__':
    
38.     n = fact(600851475143)
    
39.     print(n[-1])
    
40. 
    

复制代码

0mrli0

1. /*找一个合数的最大质数因子
   
2. 600851475143的最大质数因子是多少？
   
3. 分析：先分解质因式，再输出最大结果。*/
   
4. 
   
5. #include <stdio.h>
   
6. #define N 600851475143
   
7. 
   
8. int main()
   
9. {
   
10.     unsigned long long i, maxfactor;
    
11.     unsigned long long n = N;
    
12.     for(i=2; i<=n; i++)  
    
13.     {
    
14.         while(n%i == 0)
    
15.         {
    
16.             printf("%u ", i);
    
17.             n = n / i;
    
18.             maxfactor = n==1 ? maxfactor : n;
    
19.         }
    
20.     }
    
21.     printf("\nmaxfactor = %u\n",maxfactor);
    
22.     return 0;
    
23. }

复制代码

71 839 1471 6857
maxfactor = 6857

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

marmot

1. print("""问题： 13195 的质数因子有 5, 7, 13 和 29。
   
2. 600851475143 的最大质数因子是多少？
   
3. -------------------------------------------------""")
   
4. 
   
5. # 数字除以2，若能被整除，取结果继续除以 i = 2，若不能则除以 i+1：
   
6. # 依序递增，直到被自己除，此时的数字即为所求的最大质因子。
   
7. 
   
8. def zhiyinzi(x):
   
9.     i=2
   
10.     while x != 1 :              # x 不等于 1
    
11.         if x % i == 0:           # 能除尽2
    
12.             x = x/i               # 继续除
    
13.             zhiyinzi = i           # 得到最大质因子
    
14.         else:
    
15.             i += 1                  # 除不尽就 +1
    
16. 
    
17.     return  zhiyinzi
    
18. 
    
19. print("答案是： " + str(zhiyinzi(600851475143)))

复制代码

6leensky

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

复制代码

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

pan1990

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

余欲渔

不严谨的解法

1. zhishu=[2,3]
   
2. def jc(i):
   
3.     for x in zhishu:
   
4.         if i%x==0:return 1
   
5. for i in range(5,10000,2):
   
6.     if jc(i):continue
   
7.     if i not in zhishu:zhishu.append(i)
   
8. zhishu.reverse()
   
9. for i in zhishu:
   
10.     if 600851475143%i==0:
    
11.         print(i)
    
12.         break

复制代码

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

复制代码

夜魔时生

1. l=[]
   
2. a=600851475143
   
3. for i in range(2,a//2):
   
4.     if a%i==0:
   
5.         l.append(i)
   
6. print(max(l))
   
7.    

复制代码

99592938

Liu_xy 发表于 2016-5-4 22:23
6857
[71, 839, 1471, 6857]
read:0.209758 s

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

翼--

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main()
   
5. {
   
6. long long num = 0;
   
7. printf("***input the number:\n");
   
8. scanf("%lld",&num);
   
9. long long flag = 0;       //存放最大质因数
   
10. 
    
11. //对于偶合数先进行转换成奇数操作
    
12. while(num % 2 == 0)
    
13. {
    
14. num = num / 2;
    
15. flag = 2;
    
16. }
    
17. 
    
18. //对于奇合数进行操作，模上从3开始的奇数
    
19. while(1)
    
20. {
    
21. if(num % i == 0)
    
22. {
    
23. //对于合数中的因数进行质数判断，是质数的存放到flag中
    
24. long long j = 2;
    
25. for(; j <= i / 2; j++){
    
26. if(i % j == 0)
    
27. break;
    
28. }
    
29. if(j > i / 2){
    
30. flag = i;
    
31. num = num / i;
    
32. }
    
33. }
    
34. if(num < i)
    
35. break;
    
36. i = i + 2;
    
37. }
    
38. printf("***the largest prime factor is %lld",flag);
    
39. }

复制代码

JonTargaryen

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main(void)
   
5. {
   
6.     long int number;
   
7.     int factor;
   
8. 
   
9.     // number = 13195;
   
10.     number = 600851475143;
    
11. 
    
12.     for(factor = 2; factor <= sqrt(number); factor++)
    
13.     {
    
14.         if(!(number % factor))
    
15.         {
    
16.             number /= factor;
    
17.             printf("%d ", factor);
    
18.         }
    
19.     }
    
20.     printf("\n");
    
21. 
    
22.     printf("%ld\n", number);
    
23. 
    
24.     return 0;
    
25. }

复制代码

JonTargaryen

1. import math
   
2. 
   
3. # number = 13195
   
4. number = 600851475143
   
5. 
   
6. factor = 2
   
7. largest = int(math.sqrt(number))
   
8. 
   
9. while factor <= largest:
   
10.     if not (number % factor):
    
11.         number /= factor
    
12.         print(factor, end = ' ')
    
13. 
    
14.         factor = 1
    
15.         largest = int(math.sqrt(number))
    
16. 
    
17.     factor += 1
    
18. 
    
19. print("\nThe largest prime factor is:", int(number))

复制代码

Eagle.Tong

Python
#求600851475143的最大质数因子

1. import math
   
2. import time
   
3. 
   
4. 
   
5. def ifprime(n):
   
6.         r = int(math.sqrt(n))
   
7.         for i in range(2,r+1):
   
8.             if n%i == 0:
   
9.                 return 0
   
10.         return 1
    
11. 
    
12. start = time.time()
    
13. number = 600851475143
    
14. dividend = int(math.sqrt(number)) + 1
    
15. Flag = 0
    
16. while dividend > 1:
    
17.     if number%dividend == 0:
    
18.         Flag = ifprime(dividend)
    
19.         if Flag == 1:
    
20.             print(dividend)
    
21.             break
    
22.     dividend -= 1
    
23. 
    
24. end = time.time()
    
25. print(end-start)

复制代码

6857
0.4s

天之南

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long long x = 600851475143;
   
6.         long long maxF = x;
   
7.         for (int i = 2; i * i < maxF; i++)
   
8.         {
   
9.                 while (maxF%i == 0) {
   
10.                         maxF /= i;
    
11.                 }
    
12.         }
    
13.         printf("%ld\n", maxF);
    
14. 
    
15.         return 0;
    
16. }

复制代码

铭记太阳

答案是688543

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

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int i;
   
6.         unsigned long Num=600851475143;
   
7.         for(i=2;i<(Num/2);++i)
   
8.         {
   
9.                 if(Num%i==0)
   
10.                 {
    
11.                         while(Num%i==0)        Num=Num/i;
    
12.                 }
    
13.         }
    
14.         printf("%d\n",Num);
    
15.         return 0;
    
16. }

复制代码

俞晨曦

1. bool IsPrime(int num)
   
2. {
   
3.         int count = (int)sqrt(num);
   
4.         int flag = 0;
   
5. 
   
6.         for (int i = 2;i <= count && !flag;++i)
   
7.         {
   
8.                 if(num % i == 0)
   
9.                         flag = 1;
   
10.         }
    
11.         if(flag)
    
12.                 return false;
    
13.         else
    
14.                 return true;
    
15. }
    
16. 
    
17. int three(int num)
    
18. {
    
19.         int fact = 1;
    
20. 
    
21.         for(int i = 2;i <= num - 1;++i)
    
22.         {
    
23.                 if(num % i == 0 && i > fact && IsPrime(i))
    
24.                         fact = i;
    
25.         }
    
26.         return fact;
    
27. }

复制代码

水冢

#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

1. def checkprime(target):
   
2.     for i in range(2,int(target/2 + 1)):
   
3.         if not(target % i):
   
4.             return False
   
5.         elif i > int(target/2 - 1):
   
6.             return True
   
7.         
   
8. def maxprime(tar):
   
9.     fact = int(tar/2 + 1)
   
10.     while fact > 2:
    
11.         if not(tar % fact):
    
12.             if checkprime(fact):
    
13.                 break
    
14.         fact -= 1
    
15.     print(str(tar)+'的最大质数因子是：' + str(fact))
    
16. #maxprime(5555)   
    
17. maxprime(600851475143)

复制代码