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

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)

复制代码

Kotori

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

long long isPrime(long long num);

int main(void)
{
        long long i;
        long long target = 600851475143;
       
        for (i=3;i<target;i+=2)
        {
                if (target % i == 0)
                {
                        if((isPrime(target / i)) == 1)
                        {
                                printf("%lld的最大质数因子：%lld",target, target / i);
                                break;
                        }
                }
        }
        return 0;
}

long long isPrime(long long num)
{
        long long i;
        long long temp = (long long) sqrt(num);
       
        for(i=3;i<=temp;i+=2)
        {
                if (num % i == 0)
                {
                        return 0;
                }
        }
       
        return 1;
}

jerryxjr1220

AArdio编译：

1. import console;
   
2. import time.timer
   
3. 
   
4. console.setTitle("test");
   
5. 
   
6. time.timer.start();
   
7. 
   
8. var n = 600851475143;
   
9. var max_p = 0
   
10. while (n != 1){
    
11.         for(i=2;n;1){
    
12.                 if(n%i==0){
    
13.                         max_p = math.max(max_p,i );
    
14.                         n/=i;
    
15.                         break;       
    
16.                 }
    
17.         }
    
18. }
    
19. console.print(max_p);
    
20. 
    
21. console.print(time.timer.endTick())
    
22. 
    
23. console.pause();

复制代码

6857
0.42870622873306 （单位是毫秒）
请按任意键继续 ...

zjhnz

错了

zjhnz

答案 6857  用时 0.2595秒
#include <stdio.h>
#include <math.h>

int isPrime(unsigned long long n);

int isPrime(unsigned long long n)
{
        unsigned long long temp=sqrt(n);
       
        for ( unsigned long long i=2; i<=temp; i++ )
        {
                if ( n%i ==0)
                {
                        return 0;
                }
               
        }
        return 1;
}

int main(void)
{
        unsigned long long n=600851475143;
        unsigned long long max,i;
       
   while(1)
   {
          
           for (i=3; i<=n; i=i+2)
       
        {       
                if( (n%i)==0 &&isPrime(i) )
                {
                        //printf(" %ld  ",i);
                    n=n/i;
                    break;
                }               
        }       
        if(n==1)
        {
                max=i;
                break;
        }         
                          
          
   }       
        printf("%ld",max);
       
        return 0;
}