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

/*判断是否是素数*/
    public static Boolean prime(long x){
        for(int i=2;i<=Math.sqrt(x);i++){
            if(x%i==0) return false;
        }
        return true;
    }
/**
         * test3 查找最大素数因子
         */
        long flag=0;
        long num=600851475143l;
        for(long i=2;i<=Math.sqrt(num);){
            //System.out.println(i);
            if(num%i==0){
                System.out.println(i);
                if(prime(num/i)==true)
                {
                    flag=num/i;
                    System.out.println("flag"+num/i);
                    i+=Math.sqrt(num);
                }else{
                    if(prime(i)==true){
                        flag=i;
                        i+=2;
                    }
                    else
                        i+=2;
                }
            }else
                i+=1;
        }
        if(flag==0)
            System.out.println("最大素数因子为："+num);
        else
            System.out.println("最大素数因子是："+flag);
    }

artistlu

1. #include <stdio.h>
   
2. 
   
3. int isPrime(long long);
   
4. 
   
5. int isPrime(long long num)
   
6. {
   
7.     long long i;
   
8.     for (i  = 2; i <= num / i; i++)
   
9.     {
   
10.         if (num % i == 0)
    
11.         {
    
12.             break;
    
13.         }
    
14.     }
    
15. 
    
16.     return i > num / i;
    
17. }
    
18. 
    
19. int main(void)
    
20. {
    
21.     long long maxPrime;
    
22.     long long  target;
    
23.     scanf("%lld", &target);
    
24. 
    
25.     if (isPrime(target))
    
26.     {
    
27.         maxPrime = target;
    
28.     }
    
29.     else
    
30.     {
    
31.         for (long long i = 2; i <= target / i; i++)
    
32.         {
    
33.             if (target % i == 0)
    
34.             {
    
35.                 if (isPrime(i))
    
36.                 {
    
37.                     maxPrime = i;
    
38.                 }
    
39. 
    
40.                 if (isPrime(target / i))
    
41.                 {
    
42.                     maxPrime = target / i;
    
43.                 }
    
44.             }
    
45.         }
    
46. 
    
47.     }
    
48. 
    
49.     printf("%lld\n", maxPrime); //600851475143  6857
    
50.     return 0;
    
51. }
    

复制代码

由我们主宰

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

int CheckPrime(int m)
{
        int i,leap=1;
        for(i=2;i<=sqrt(m);i++)
        {
                if(m%i==0)
                {
                        leap=0;
                        break;
                }
        }
        return leap;
}
int main()
{
        int m,n;
        printf("请输入一个合数:");
        scanf("%d",&n);
        for(m=n;m>1;m--)
        {
                if(n%m==0)
                {
                        if(CheckPrime(m))
                        {
                                printf("%d\n",m);
                                break;
                        }
                }
        }
        return 0;
}

阿bang

1. def isprime(num):
   
2.     if num < 2:
   
3.         return False
   
4.     elif num == 2:
   
5.         return True
   
6.     for i in range(3, int(num ** 0.5) + 1, 2):
   
7.         if num % i == 0:
   
8.             return False
   
9.     else:
   
10.         return True
    
11. 
    
12. 
    
13. def maxprimefac(num):
    
14.     for i in range(int(num ** 0.5), 2, -1):
    
15.         if num % i == 0:
    
16.             anthornum = num / i
    
17.             if isprime(i) and isprime(anthornum):
    
18.                 return max(i, num / i)
    
19.             elif isprime(i):
    
20.                 return i
    
21.             elif isprime(anthornum):
    
22.                 return anthornum
    
23.     else:
    
24.         return num
    
25. print maxprimefac(600851475143)

复制代码

soulwyb

def maxzhisu(n):
    s = 0
    if n < 4:
        print "这不是合数"
        return False
    for i in range(4, n):
        if n % i == 0:
            for w in range(2,i+1):
                if i % w == 0:
                    if w in [2,3]:
                        s = w
                else:
                    s = w
    if s:
        return "最大质数是%d" % s
    else:
        return "这不是一个合数，泥煤"
   
m = maxzhisu(100)
print m

                    

#-*- codding:utf-8 -*-

import math
import time
start = time.clock()
list1 = []
Num = 600851475143

def isPrime(x):
       
        for i in range(2, int(math.sqrt(x))):
               
                if i == int(math.sqrt(x))-1:
               
                        list1.append(x)
                       
                if x % i == 0:
               
                        list1.append(i)
                        x = x / i
                       
                        if x >= 1 :
                       
                                isPrime(x)
                               
                        break
                         

isPrime(Num)
print(max(list1))                                               
print(list1)

end = time.clock()
print("read:%f s" % (end - start))

yunying12321

1. def isprime(n):
   
2.     if n == 1:
   
3.         return False
   
4.     elif n == 2:
   
5.         return True
   
6.     elif n > 2:
   
7.         for i in range(2, n//2+2):
   
8.             if n%i == 0:
   
9.                 return False
   
10.         else:
    
11.             return True
    
12. 
    
13. def ds(n):
    
14. 
    
15.     if n == 1 or n == 2:
    
16.         yield n
    
17.     elif n > 2:
    
18.         for i in range(2, n//2+2):
    
19.             if n%i == 0 and isprime(i):
    
20.                 yield i
    
21.                 x = n//i
    
22.                 while x%i == 0:
    
23.                     yield i
    
24.                     x //= i
    
25. 
    
26. def main():
    
27.     n = int(input('输入一个整数：'))
    
28.     l = []
    
29.     f = ds(n)
    
30.    
    
31.     while True:
    
32.         try:
    
33.             s = next(f)
    
34.         except:
    
35.             break
    
36.         l.append(str(s))
    
37.    
    
38.     print(n, '=', '*'.join(l))
    
39.     print('最大的质因子：', l[-1])
    
40.    
    
41. if __name__ == '__main__':
    
42.     while True:
    
43.         main()

复制代码

使用迭代器，奇怪的是，输入600851475143以后，答案一直不出来，我按了ctrl+c停止后，马上就出答案了
不知道是什么环节出问题了

ufo20085

import time
import math
from numba import jit

def get_yinzi(x):
    listall= [1]
    for i in range(2,int(math.sqrt(x)),1):
        if x%i == 0:
            listall.append(i)
    listall.append(x)
    return listall

i = 600851475143

starttime=time.time()
a=get_yinzi(i)
a.reverse()
for each in a:
    if len(get_yinzi(each)) == 2:
        print(each)
        break
endtime=time.time()
print(endtime-starttime)


0.2s
思路：定义一个函数，求数的因子列表。对该数的因子从大到小求因子的因子列表，如果列表长为2，则该数为质数。

ssd8661366

1. import math
   
2. 
   
3. #质数Generator
   
4. def Prime():
   
5.     yield 2
   
6.     num = 3
   
7.     while True:
   
8.         judge = True
   
9.         for i in range(2,int(math.sqrt(num))+1):
   
10.             if num%i == 0:
    
11.                 judge = False
    
12.                 break
    
13.         if judge:
    
14.             yield num
    
15.         num += 2
    
16. 
    
17. 
    
18. #质因子分解
    
19. def analysis(num):
    
20.     num_list = [1]
    
21.     myP = Prime()
    
22.     while num != 1:
    
23.         prime = next(myP)
    
24.         while num%prime == 0:
    
25.             num_list.append(prime)
    
26.             num /= prime
    
27.     return num_list
    
28. 
    
29. print(analysis(600851475143))
    

复制代码

结果：[1, 71, 839, 1471, 6857]
最大质数：6857
运行时间：0.00500798

li1347zhen

1. #include<stdio.h>
   
2. #include<math.h>
   
3. int prime(long long int  x);
   
4. long long int nextprime(long  long int x);
   
5. int main()
   
6. {
   
7.         long int x=2;
   
8.         long long int divisor = x;
   
9.         long long  int dividend = 600851475143;
   
10.         long long int quotient=0;
    
11.         while (1) {
    
12.                 if (dividend%divisor == 0) {
    
13.                         printf("%lld\n", divisor);
    
14.                        
    
15.                         quotient = dividend / divisor;
    
16.                         if (quotient == 1)
    
17.                                 break;
    
18.                         dividend = quotient;
    
19.                         divisor = 2;
    
20.                        
    
21. 
    
22. 
    
23.                 }
    
24.                 divisor = nextprime(divisor);
    
25.         }
    
26.         //printf("%d\n", prime(y));
    
27.     return 0;
    
28. }
    
29. int prime(long long int x)//返回1 表 x为素数
    
30. {
    
31.         long  int i = 2;
    
32.         double y = sqrt(x);
    
33.         while (i <= y) {
    
34.                 if (x%i == 0)
    
35.                         return 0;
    
36.                 i++;
    
37.         }
    
38.         return 1;
    
39. 
    
40. }
    
41. long long int nextprime(long long int x)
    
42. {
    
43.         while (1) {
    
44.                 x++;
    
45.                 if (prime(x)) {
    
46.                         break;
    
47.                 }
    
48.         }
    
49.         return x;
    
50. }
    

复制代码

zzzgod

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
        int max=0;
        vector<int> dest;
        const long long num=600851475143;
        for(int i=2;i<(int)sqrt(num);++i)
        {
                if(num%i==0 && !distance(find(dest.begin(),dest.end(),i),dest.end()))
                {
                        dest.push_back(i);
                }
        }
        cout<<dest.back();
}

答案：486847

zzzgod

zzzgod 发表于 2018-6-20 15:54
#include
#include
#include

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

bool zhishu(int x)
{
        for(int i=2;i<sqrt(x);++i)
        {
                if(x%i==0)
                {
                        return 0;
                }
        }
        return 1;
}

int main()
{
        int max=0;
        vector<int> dest;
        const long long num=600851475143;
        for(int i=2;i<(int)sqrt(num);++i)
        {
                if(num%i==0 && zhishu(i))
                {
                        dest.push_back(i);
                }
        }
        cout<<dest.back();
}

ThatGirl

from math import sqrt
from time import time

# 素数判断函数，给一个值，如果返回True，则表示是素数，False表示为非素数
def is_prime(n):
    if n > 1:
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for i in range(3, int(sqrt(n))+1, 2):
            if n % i == 0:
                return False
        # for循环结束后，如无False，则返回True
        return True
    # 如 if n > 1 不成立，则返回False
    return False
        
# 取得给定值的所有乘数因子
def factor(n):
    L = []
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            L.append(i)
            L.append(n/i)
    # set 去除相同的因子
    return set(L)
   
start_time = time()
memb = list(filter((is_prime), factor(600851475143)))
memb.sort()
end_time = time()

print(memb)
print('Running time = ', end_time - start_time)
print('Largest prime factor is ', memb[-1])
>>>
[71, 839, 1471, 6857]
Running time =  0.113600015640
Largest prime factor is  6857

塔利班

1. def fun(x):
   
2.     a=[]
   
3.     while x!=1:
   
4.         for i in range(3,int(x**(0.5))+1,2):
   
5.             if x%i==0:
   
6.                 a.append(i)
   
7.                 x//=i
   
8.     return max(a)

复制代码

shanczp

输出        71 839 1471 6857,相乘得出的结果正确，中间遇到了一个很麻烦的问题。。就是定义int老是报溢出。。我一直不知道哪个可以，最后用了__int64才成功赋值了
        int n=0;
        __int64 num=600851475143;
        while (true)
        {
                int i=2;       
                for(;i<=num;i++)
                {
                        if(num%i==0)
                        {
                                n=i;
                                break;
                        }
                }
                printf("%ld\n",n);
                num=num/n;
                if(num==1)
                        break;
        }

cupbbboom

有没有跟我一样：先百度  合数 、质数因子，然后就有了百度  什么是质数？什么是因数？什么是整数、正整数?然后就......崩溃了，不想看下去

996982937

#include<stdio.h>
#include<math.h>
void main()
{
        long unsigned int i,a;
        int flag=1;
        for(i=2;i<=(600851475143/2)&&i>1;i++)
        {
                if(600851475143%i==0)
                {
                        for(a=2;a<=(long unsigned int)sqrt(i);a++)
                        {
                                if(i%a==0)
                                {
                                        flag=0;
                                        break;
                                }
                        }
                        if(flag==1)
                        {
                                printf("%d\n",i);
                        }
                        flag=1;
                }
        }
}

输出结果
71
839
1471
6857

大大大敏

#include <stdio.h>
int main()
{
    long long i,n;
    scanf("%lld",&n);
    for(i = 2; i <= n; i ++)/*从小数除起可以确保该数为质数所以不必判断是否为质数*/
    {
            while(n != i)
        {
            if(n % i == 0)
                n = n / i;
            else
                    break;
        }
        }  
    printf("%lld",n);
}

ietar

python 6857

1. def p3():
   
2.     import math
   
3.     a = 600851475143
   
4.     def is_prime(n):
   
5.         if not n%2:
   
6.             return False
   
7.         n1 = int(math.sqrt(n))
   
8.         for i in range(3,n1+1,2):
   
9.             if not n%i:
   
10.                 return False
    
11.         return True
    
12.     # 肉眼可见2不是a的约数
    
13.     def p3_1(n):
    
14.         if is_prime(n):
    
15.             return n
    
16.         for i in range(3,a//3+1):
    
17.             if not n%i:
    
18.                 return p3_1(n/i)
    
19.     print(p3_1(a))

复制代码